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

[@piyushnautiyal5112]

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

[@prakhargarg4166]

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

[@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.