class Solution { public: long long solve(vector& nums, int index, bool flag,vector&dp) { if(index == nums.size()) return 0; if(dp[index][flag] != -1) return dp[index][flag]; long long cut = nums[index] + solve(nums,index+1,false,dp); long long notCut = (flag == false) ? -nums[index] + solve(nums,index+1,true,dp) : nums[index] + solve(nums,index+1,false,dp); return dp[index][flag]=max(cut,notCut); } long long maximumTotalCost(vector& nums) { vector dp(nums.size(),vector(2,-1)); return solve(nums,0,true,dp); } }; 2d dp solution this too works!! will surely see your recursive to iterative solution dp video...explanation of this video was very nice :) was able to come up with my solution after watching your video ;)
bro i used paritions of dp method for solving this but it gave MLE, how to optimise it private long dp[][]; private long f(int i, int j, int[] a) { if (i == j) return a[i]; if (j - i + 1 == 2) { return Math.max(a[i] - a[j], a[i] + a[j]); } if (dp[i][j] != -1) return dp[i][j]; long max = Long.MIN_VALUE; for (int k = i; k < j; k++) { long left = f(i, k, a); long right = f(k + 1, j, a); max = Math.max(max, left + right); } return dp[i][j] = max; } public long maximumTotalCost(int[] nums) { dp = new long[nums.length][nums.length]; for(long i[]:dp) Arrays.fill(i, -1); return f(0, nums.length - 1, nums); }
You are currently creating an array of 10^5 * 10^5, thats why the MLE. We cannot create an array of size 10^10, max I think is till 10^6. Also, the next state is only dependant on whether we had a +1 or -1 as sign. It does not depend on the previous value. So, just create a DP of size n*2 , n for the indexes and 2 for sign. And just do split/not split.
Superb explanation , Thank you
i solved this utilizing a logic similar to maximum subarray product
nice solution and great explaination
Just want to ask if partition DP will work on it or not?
dude please keep making the contest videos you're a messiah for thousands of undergrads like me
What about that -1(r-l) does it not effect answer
what was the video again? to convert recursion to bottom up dp intuition by?
nice
There is no need for isStart variable. only i and sign are enough to solve this problem. and reduce complexity to i*sign
thank you
dp without any additional flags/states:
dp[i + 1] = max(dp[i + 1], dp[i] + a[i]);
dp[i + 2] = max(dp[i + 2], dp[i] + a[i] - a[i + 1]);
class Solution {
public:
long long solve(vector& nums, int index, bool flag,vector&dp) {
if(index == nums.size()) return 0;
if(dp[index][flag] != -1) return dp[index][flag];
long long cut = nums[index] + solve(nums,index+1,false,dp);
long long notCut = (flag == false) ? -nums[index] + solve(nums,index+1,true,dp) : nums[index] + solve(nums,index+1,false,dp);
return dp[index][flag]=max(cut,notCut);
}
long long maximumTotalCost(vector& nums) {
vector dp(nums.size(),vector(2,-1));
return solve(nums,0,true,dp);
}
};
2d dp solution this too works!! will surely see your recursive to iterative solution dp video...explanation of this video was very nice :) was able to come up with my solution after watching your video ;)
In the contest, in third question, my last 5 testcases, give MLE. Solved first and second question
Can you do Leetcode biweekly 4th problem regarding permutations ?
Its there already, count the no. of inversions
I am getting Memory Limit Exceeded,
#define ll long long int
class Solution {
public:
vector dp;
ll solve( vector nums, int i, int start, int sign )
{
if( i == nums.size() )
return 0;
if( dp[i][start][sign] != -1e15 )
return dp[i][start][sign];
ll answer = -1e15;
if( start == 0 )
answer = max( answer, nums[i] + solve( nums, i+1, 1, sign^1 ) );
else
{
if( sign == 0 )
answer = max( answer, nums[i] + solve( nums, i+1, 1, sign^1 ) );
else
answer = max( answer, -nums[i] + solve( nums, i+1, 1, sign^1 ) );
answer = max( answer, solve( nums, i, 0, 0 ) );
}
return dp[i][start][sign] = answer;
}
ll maximumTotalCost(vector& nums)
{
dp = vector(nums.size()+1, vector(2, vector(2, -1e15)));
return solve(nums, 0, 0, 0);
}
};
Can anyone help me please?
anyone can tell what is wrong in this code and logic
#define ll long long
class Solution {
public:
ll helper(int i, int j, vector& nums) {
if(i > j) return 0;
ll sum = 0;
ll maxi = -1e9;
for(int k = i;k maxi) maxi = result;
}
return maxi;
}
long long maximumTotalCost(vector& nums) {
int n = nums.size();
return helper(0,n-1,nums);
}
};
bro i used paritions of dp method for solving this but it gave MLE, how to optimise it
private long dp[][];
private long f(int i, int j, int[] a) {
if (i == j) return a[i];
if (j - i + 1 == 2) {
return Math.max(a[i] - a[j], a[i] + a[j]);
}
if (dp[i][j] != -1) return dp[i][j];
long max = Long.MIN_VALUE;
for (int k = i; k < j; k++) {
long left = f(i, k, a);
long right = f(k + 1, j, a);
max = Math.max(max, left + right);
}
return dp[i][j] = max;
}
public long maximumTotalCost(int[] nums) {
dp = new long[nums.length][nums.length];
for(long i[]:dp)
Arrays.fill(i, -1);
return f(0, nums.length - 1, nums);
}
You are currently creating an array of 10^5 * 10^5, thats why the MLE. We cannot create an array of size 10^10, max I think is till 10^6.
Also, the next state is only dependant on whether we had a +1 or -1 as sign. It does not depend on the previous value. So, just create a DP of size n*2 , n for the indexes and 2 for sign. And just do split/not split.