Partition Array for Maximum Sum | Why DP | Recursion | Memo | Bottom Up | Leetcode 1043

Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 85th Video of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will try to solve a very good and classic DP problem based on array partition - Partition Array for Maximum Sum | Leetcode 1043
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Partition Array for Maximum Sum | Leetcode 1043
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/partiti...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach-1 Summary : The approach uses a recursive dynamic programming strategy with memoization to avoid redundant calculations. The function solve recursively explores different partitioning options, keeping track of the maximum sum encountered. The memoization array t is used to store and retrieve previously computed results, reducing the time complexity. The main function initializes necessary variables, sets up memoization, and calls the recursive solve function to obtain the maximum sum after partitioning.
Approach-2 Summary : The approach uses dynamic programming to iteratively compute the maximum sum for each partition. The array t is used to store intermediate results, where t[i] represents the maximum sum for the partition arr[0 to i]. The code iterates through each position in the array, considering partitions of size at most k. It calculates the current maximum within the partition and updates the maximum sum for the current position based on the best result from previous partitions. The final result is the maximum sum for the entire array, stored in t[n]. This approach avoids recursion and efficiently computes the maximum sum after partitioning.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear

[@theOmKumar]

//TOP DOWN TO BOTTOM UP int solve (vector& arr, int k , int idx){ if (idx == arr.size()){ return 0; } if (dp[idx] != -1) return dp[idx]; int maxE = INT_MIN, sum = INT_MIN, n = arr.size(); for(int i = idx; i < min(n,idx+k); i++){ maxE = max(maxE, arr[i]); sum = max(sum, maxE*(i-idx+1) + solve(arr,k,i+1)); } return dp[idx] = sum; } //USING SAME CODE COPY PASTE! int maxSumAfterPartitioning(vector& arr, int k) { int n = arr.size(); //base case n+1 is 0 in dp! vectordp(n+1,0); for(int idx = n-1; idx >= 0; idx--){ int maxE = -1; for(int i = idx; i < min(n,idx+k); i++){ maxE = max(maxE, arr[i]); dp[idx] = max(dp[idx], maxE*(i-idx+1) + dp[i+1]); } } return dp[0]; }

[@codestorywithMIK]

Way to go 🔥🔥 That’s what i was talking about. Since you have done the Homework, Let me know your email id, i will send you Amazon voucher.

[@user-ub2is4rs4x]

I could also solve like this. All thanks to you mik ❤️

[@harshtiwari416]

bhai aapke solve wale function mein toh for loop mein bhi right jaa rhe ho aur solve mein bhi right jaa rhe ho but jana toh rhs se lhs tha na toh kisi ek jagah (shayad for loop mein ) lhs jaoge???

[@harshtiwari416]

bhai agar right to left ka solve likha ho toh dedo , bottom up mein likh lunga

[@dvghf123]

mera ho gaya ye!!! i'm watching you dp playlist from last 1.5 weeks,and this was my 1st dp problem that i have solved myself, thank you so much for everything!!! Your way of teaching is so good!!! thnk youuu

[@abc-ym4zs]

which dp playlist bro

[@user-ub2is4rs4x]

@@abc-ym4zs his DP concepts playlist as well as Interview DP problems playlist. Check his playlist section. They improved my dp a lot

[@vivekgupta_3085]

from the last some days potd is of dp so he is talking about that only@@abc-ym4zs

[@anonymous090]

Thank youuu for the amazing explaination.

[@aws_handles]

Thanks a lot. Was waiting for you 👌🏻👌🏻

[@souravjoshi2293]

You are the best mik. Thank you for working so hard and helping us also

[@theOmKumar]

was able to solve by recursion + memo thanks to you.

[@gauravbanerjee2898]

Thanks a lot bhaiya ❤❤

[@k-CE-OmkarPathak]

Awesome explanation. Thanks Bhaiya

[@user-ub2is4rs4x]

Amazing explanation as always. You have improved my DP ❤️

[@kumkumslab5811]

lovely explaination sir

[@harsh-singh]

Thank you for intuition 😀.

[@aws_handles]

I was able to solve with bottom up just by following your playlist. I derived from the recursion memo but couldn’t think of your bottom up. That was unique 👌🏻

[@CodeMode9313]

it was a great explantion bro ,,thanks

[@ShivamTiwari-yl7xv]

Nice Explaination thanks

[@kunalpatil.24]

Thank you

[@jagadeeshp1163]

Observations: The best part I learnt today is when I need the maximum sum I calculated the max in the subarray again but got to know it take every time o(n) time which increase the tc so instead we can maintain a maxi and do it in o(1) operations Done✅🙇‍♂

[@nayan_CSE]

// Bottom-Up approach😊 int solveTab(vectorarr,int k){ vectordp(arr.size()+1,0); for(int index=arr.size()-1;index>=0;index--){ int max_val=0; int res=0; for(int j=index;j

[@S3aw0lf]

When i is at 15 for [1,15,7,9,2,5,10] are we exploring from i to j as [15,7,9]subarray?

[@bhartendupant8859]

❤

[@molyoxide8358]

bhiya at most k na lekr poora k size subarray hi le lete tab pakka hi maxSum aayega na. Agar aise karenge toh kam recusrion mein kaam bhi hojayyega.

[@MakeuPerfect]

bhaiya recursion k under jane par confuse ho jata hun itana sarar recusrion calls story kaise banau

[@bhuppidhamii]

i know i was dp but there is no way I could come up with approach

[@dayashankarlakhotia4943]

please make video on leetcode 2035 partition array into two array with minimum sum.this problem dp doesn't work.

[@kapilsinghbaghel3090]

bhai video or explanation toh mast hai, question smj me aa gya but red pen use mat kiya karo visibility kam ho jati hai , yellow, blue, white theek hai

[@codestorywithMIK]

Feedback taken. No red pen from now onwards ❤️🙏

[@adityasingh-cg3co]

Sir N stacks in an array wala question ka explanation de dijiye.

[@harsh_saini3878]

😇

[@abc-ym4zs]

i will tell my situation can u guide me sir after seeing question i written this solution class Solution { public: int maxSumAfterPartitioning(vector& arr, int k) { vectorans; sort(arr.begin(),arr.end()); int sum=0; int cnt=(arr.size()/k); int cnt1=(arr.size()%k); int i=arr.size()-1; while(cnt--) { sum+=(arr[i]*k); i--; } while(cnt1--) { sum+=arr[i]; i--; } return sum; } }; then i seen question tag got to know it is from dp then i opened your youtube channel and watched first 5 min of your video then i able to solve the problem where i am lacking in coding now i am in third year i dont know how to improve what patterns should i cocentrate more sir can u guide me or any process can u tell me sir please

[@dayashankarlakhotia4943]

please give me roadmap of web development

[@aishwaryap.s.v.s7387]

in bottom up why did u multiple currmax*j +t[i-j] we can also do currmax+t[i-j] also ryt?

[@newglobal7271]

Bhaiya ajj(4th feb) ka GFG POTD pls karwa dena pls pls

[@codestorywithMIK]

I have my train today back to home. Will definitely check that out when I am home. My trip is over 🥶😇🙏

[@newglobal7271]

ok bhaiya@@codestorywithMIK

[@shaamidrees6036]

In example [1, 15, 7,9,2,5,10]. 9 got skipped for eg we took 15 as max of the 3 size subarray and called for 9,2,5,10 where 2,5,10 has max 10 what about 9 which part of call is this can't understand this

[@codestorywithMIK]

If you extend the tree diagram, you will notice this in the 3rd branch onwards : You took (1,15,7) as first subarray having max = 15 Now, you called recursion from index = 3 i.e, for {9, 2, 5, 10} Now, you have following options : 1) take (9) and move ahead 2) take (9,2) and move ahead 3) take (9,2,5) and move ahead All the 3 points above will further go to their respective recursion calls to explore. Notice the 1) one when you took (9) only In this case max is 9 and you called recursion for {2,5,10} and so on…. I always suggest drawing the complete tree diagram , it helps to visualise all possible paths. If tree diagram is big, try atleast drawing to 2nd or 3rd level of tree. Everyone will be clear

[@shaamidrees6036]

@@codestorywithMIK thanks bhai got it

[@Harsh-dy7ud]

Bhaiya please provide notes tooo🙏🙏🙏

[@codestorywithMIK]

github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-1034-Partition%20Array%20for%20Maximum%20Sum.pdf ❤️🙏

[@harshtiwari416]

RHS vali apporach ki video bhi hoti toh badhiya hota???

[@codestorywithMIK]

Definitely. Actually i have my train back to home tomorrow. Let me make RHS approach as soon as I reach back. My trip will be over tomorrow 😄❤️🙏

[@harshtiwari416]

ok sir!!! @@codestorywithMIK

[@harshtiwari416]

bhai gfg ke count digits of a number ki bottom up video bhi aayegi???@@codestorywithMIK

[@AS-gf3ci]

Bottom Up Code from right to left, i.e., i = (n-1) to i >= 0. int n = arr.size(); vector dp(n+1, 0); for(int i = (n-1); i >= 0; i--) { int ans = 0; int curr_max = INT_MIN; for(int j = i; ((j < arr.size()) && (j - i + 1

[@codestorywithMIK]

Well done ❤️

[@dhairyachauhan6622]

hi bhaiya aaj ka contest ka question 3 almost solve ho gya tha but duplicate case mujse handle nhi hua time pe Agar aap kabhi iss pe video banao then this is 3026. Maximum Good Subarray Sum(contest q3) just wanted to ask in that video please explain me 1 thing since i am not so good with math 1) how to deal with absolute in sliding window in these cases a) abs(a+b)

[@toptecher1633]

bottom up in java rec+memo class Solution { int n; int[] dp; public int rec(int i, int[] arr, int k){ if(i < 0) return 0; if(dp[i] != -1)return dp[i]; int currMax = 0; int ans = 0; for(int j = i; j >= 0 && i-j+1 = 0; size--){ int currMax = 0; int ans = 0; for(int j = size; j < n && j-size+1

[@mohdtalib7350]

HW for same code in java:- public int maxSumAfterPartitioning(int[] arr, int k) { int n = arr.length; int[] dp = new int[n+1]; for (int index = n - 1; index >= 0; index--) { int curr_max = -1; for(int j = index; j

[@toptecher1633]

Nowadays I am able to code myself but the optimised version is always here .I am able to write optimsed code for easy question but don't know when i will be able to write optimised code of questions like this. mycode before watching video class Solution { int[][] dp; public int rec(int[] arr, int idx, int currSize, int currMax, int k){ if(idx >= arr.length) return 0; if(dp[idx][currSize] != -1) return dp[idx][currSize]; int notPart = 0; currMax = Math.max(currMax, arr[idx]); if(currSize < k) notPart = rec(arr, idx+1, currSize+1, currMax, k); int part = (currSize)*currMax; if(currSize > 0) part += rec(arr, idx+1, 1, 0, k); return dp[idx][currSize] = Math.max(notPart,part); } public int maxSumAfterPartitioning(int[] arr, int k){ int n = arr.length; dp = new int[n+1][n+1]; for(int i = 0; i

[@sooyashjaju4208]

Space Optimized In Bottom Up O( k ) int maxSumAfterPartitioning(vector& arr, int k) { vector dp(k); for(int i=arr.size()-1;i>=0;i--) { int maxi=0; int sum=0; for(int j=i;j=0;i--) { int maxi=0; int sum=0; for(int j=i;j

[@abhishekbajpai3864]

Bhaai mujhe dsa seekhni haai ye bataiye aapki playlist ko kis sequence maai dekhna start karun i am confused ap gajb padhate hoo pleasee hwlp kariye ek choti vedio batadijiye ki kaise aapki playslist se dsa ki maximum benefit le sake thank you..

[@souravjoshi2293]

If you are a beginner. start with Array playlist. I also started with Array.

[@shaamidrees6036]

First learn the basics of the data structures all the concepts including stl or collection And started following his playlist from array, linked list ,string, stacks, queues then recursion and then dp graph

[@codestorywithMIK]

I always suggest first 1) Basics of DS - for example: study what is stack, how to implement it, study linkedlist, tree implementation etc. Now, start solving qns from my interview problems playlist . Start like -> Array, String, Tree, LinkedList Recursion, Graph, DP , Backtracking. For tough topics like Graph, DP etc, I have two plausible : 1) Concepts playlist 2) Interview Problems For example : Graph Concepts - kzbin.info/aero/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY&si=ps2rtBTa2PnxzcD7 Graph Interview Problems - kzbin.info/aero/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO&si=4jhJA-P0OnAum5GE DP Concepts - kzbin.info/aero/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt&si=I8vQcHcdMlB1M1-f DP Interview Problems - kzbin.info/aero/PLpIkg8OmuX-L_QqcKB5abYynQbonaNcq3&si=RlJcdRfY4tmlbwlR Hope this helps Note - Recursion concepts playlist is coming this Monday evening 😇

[@Rohitkumar-nn1hs]

//Memoization // int n; // int t[501]; // int solve(vector& arr, int i, int k) { // if(i >= n) return 0; // if(t[i] != -1) return t[i]; // int res = INT_MIN; // int curr_max = INT_MIN; // for(int j = i; j < min(i + k, n); j++) { // curr_max = max(curr_max, arr[j]); // res = max(res, curr_max * (j - i + 1) + solve(arr, j + 1, k)); // } // return t[i] = res; // } // int maxSumAfterPartitioning(vector& arr, int k) { // n = arr.size(); // memset(t, -1, sizeof(t)); // return solve(arr, 0, k); // } //DP int maxSumAfterPartitioning(vector& arr, int k) { int n = arr.size(); vectordp(n + 1,0); for(int size = n - 1; size >= 0; size--){ int curr_max = INT_MIN; for(int j = size; j < min(size + k, n); j++){ curr_max = max(curr_max, arr[j]); dp[size] = max(dp[size], curr_max * (j - size + 1) + dp[j + 1]); } } return dp[0]; }

[@dayashankarlakhotia4943]

public int maxSumAfterPartitioning (int[]arr,int k){ int n=arr.length; int[]dp=new int[k+1]; for(int i=n-1;i>=0;i--){ int maxVal=-1,ans=0; for(int j=i;j

[@user-pk6gk6yg6c]

did not understand bottom up approach

[@codestorywithMIK]

Thank you for your feedback. Actually I tried with an entirely different bottom up. Would you like to share where exactly you felt was confusing ? Also, I will make another video in which bottom up will be exactly copy of Recursion+Memo code. That will be easy. Actually i have my train back to home tomorrow. Let me make it as soon as I reach back. ❤️❤️🙏🙏

[@chetnamittal9537]

Can you please explain bottom up approach...did not understand

[@chetnamittal9537]

t[i-j] will give max sum starting from the first index right so how are we adding it to find the max sum of the remaining?

[@user-pk6gk6yg6c]

@@codestorywithMIK t[i-j] will give max sum starting from the first index right so how are we adding it to find the max sum of the remaining?

[@rajchinagundi7498]

Bottom up mai arr[i-j] lene ka funda smjh nahi aya. Cmax should return the max inside the broken sized, but i dont get it how its happening

[@rajchinagundi7498]

Also i didnt get the logic agar 1 size ka array h toh usmai upto k size break(broken size ka array) kese ho skta h

[@codestorywithMIK]

Let’s take an example. Suppose the size of array is 7 And k = 3 Now there are multiple possibilities of taking at most 3 sized subarray. First you try to j = 1 sized sub array and find the best result for remaining array t[size-j] i.e. t[size-1] Then you try to take j = 2 sized sub array and find the best result for remaining array t[size-j] i.e. t[size-2] And so on.

[@ReshuSharma-jc7yu]

bhaiya i want to ask you when your recursion playlist is coming and how to dm you in your instagram account

[@8daudio672]

❤