3196. Maximize Total Cost of Alternating Subarrays | DP | 0/1 Knapsack

In this video, I'll talk about how to solve Leetcode 3196. Maximize Total Cost of Alternating Subarrays | DP | 0/1 Knapsack
Let's Connect:
📱Discord (Join Community) : / discord
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / codewitharyanbhai
💻 Twitter - / aryan_mittal007
🤖 Github: github.com/aryan-0077
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Timelines✨
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[@Jazzimus]

i solved this utilizing a logic similar to maximum subarray product

[@vaibhav7480]

dude please keep making the contest videos you're a messiah for thousands of undergrads like me

[@girishkumar8894]

thank you

[@prathyaksh5118]

what was the video again? to convert recursion to bottom up dp intuition by?

[@avvkkumawat8733]

nice

[@prakhargarg4166]

In the contest, in third question, my last 5 testcases, give MLE. Solved first and second question

[@piyushnautiyal5112]

What about that -1(r-l) does it not effect answer

[@OmSingh-ku5ms]

There is no need for isStart variable. only i and sign are enough to solve this problem. and reduce complexity to i*sign

[@AP-xh6dx]

nice solution and great explaination
Just want to ask if partition DP will work on it or not?

[@adwaitkakad4903]

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 ;)

[@learpcss9569]

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]);

[@raviprasath.k.j9462]

Can you do Leetcode biweekly 4th problem regarding permutations ?

[@ramprasath3818]

Its there already, count the no. of inversions

[@ammanchhetri6716]

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);

}
};

[@ayushmaanbn6228]

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?

[@devisriprasad119]

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);
}

[@arghadeepdey7796]

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.