Partition Array for Maximum Sum - Leetcode 1043 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/partiti...
0:00 - Read the problem
0:17 - Memoization Explanation
7:07 - Coding Memoization
12:32 - DP Explanation
22:31 - Coding DP
leetcode 1043
#neetcode #leetcode #python

[@pastori2672]

10 + 9 = 15 caught me so off guard 😭 take a rest bro

[@pastori2672]

great video tho

[@satyamjha68]

Solved this by myself!!

[@NeetCodeIO]

Love to hear it!!

[@satyamjha68]

@@NeetCodeIO I actually had a doubt whether it is necessary to write tabulation solution in the interview. Isn't memoization solution enough ? Does it depend on the interviewer and level of question? Cause generally I don't practice writing tabulation solution . I write the recursive approach , memoize it and call it a day.

[@SlateCode]

No😢

[@NeetCodeIO]

In many cases memoization may be enough. The bottom-up solution for this problem isnt as difficult as I have shown, the main complexity in my solution came from the memory optimization / circular array. The main reason I show the bottom up solution is people sometimes complain if omit the most optimal solution.

[@saminhasan87]

Hey Neato!!! I could figure out the memoization solution by myself today and credit goes to you!!! I follow your video regularly and have learnt a lot. Your 1D DP playlist was a game-changer for me, showing me how to break down complex problems into manageable subproblems. Now I don't afraid a DP problem and try my best to solve that myself. I am grateful to you.

[@yaswanthkosuru]

you stared this question .this problem is some what different and great

[@SanketBhat7]

I am happy because I was able to come up with recursive solution with memorization on my own.

[@anlee728]

Thank you for providing multiple solutions!!

[@kareemadesola6522]

phew, they really do want us preoccupied during the weekends

[@MP-ny3ep]

Thank you !!

[@krateskim4169]

Thank you so much

[@Kaviarasu_NS]

Thanks❤

[@tranminhquang4541]

Even though I know it's a dp problem, I still struggle to figure it out ! Thanks for your ingenious solution as always!

[@SaranNarayan]

sub_sum = dp[(j - 1) % k] would work without the j > 0 check in python.. say j is 0 then j-1%k will be -1 only.

[@kirillzlobin7135]

Amazing

[@SalmanMKC]

back with another video

[@LokendraSingh-42]

At 7:20 time complexity of brute force should be O(N^k)

[@emenikeanigbogu9368]

I feel like an iterative approach would work here if you used a sliding window. Reversed the array and then did the sliding window again.

[@mailatkaushal]

i do my dp solution both ways for better understanding..

[@6a.s.harishkumar62]

Kind Request : Please explain leetcode 1190 it is not in neetcode it is asked in our campus placement drive !

[@rorothepropro]

1:25 I was out here thinking 9+10=21 but it turns out it's 15

[@razataggarwal7365]

1:24 9+10 = 15 🤣

[@midhileshmomidi3120]

what is difference between this and sliding window maximum

[@user-gs7xf6qt4l]

They are essentially different. In sliding window maximum, we want an O(1) method to query for a "FIXED" window size. This is achieved by monotonic decreasing queue of lenmonotonic queue "INCREASING" window size => prefix/suffix Hope it helps :)

[@tizekodnoon8305]

Neato! Brain Fried 🤯

[@ayush7800]

Can we do this? We want to maximize the sum, so we can sort the array in nlogn time. Afterwards we take last element of sorted array and replicate it k times if possible, otherwise replicate it enough to fit our result array. Then we move the second last element, replicate it k times and add it to result array and so on. Finally we return the sum of result array?

[@NeetCodeIO]

To get subarrays unfortunately you cant reorder the elements

[@ayush7800]

​@@NeetCodeIOBut at the end what we want is the maximised sum, and if we replicate the greatest elements, the sum would be greatest too. This is true if I am not missing anything. For example even if we don't reorder, maximum sum can be obtained if we replicate the greatest element, second greatest element.... etc. when we are traversing the array?

[@NeetCodeIO]

I think the order of elements matter. Consider this example: arr = [10, 10, 1, 1, 1, 1], k = 3.

[@samarthjain5015]

1:22 What?

[@NeetCodeIO]

Omfg, if my parents saw that they would bring out the chappal 🥿

[@ara0n]

@@NeetCodeIO bhai what is this hera pheri xD

[@theshlok]

what in the indian trauma is this@@NeetCodeIO

[@kahafb]

Isn't your solution a bit overly complicated? I feel like people should really get over calculating it "backwards". This is how I did it: class Solution: def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int: # Step 2: Tabulate n = len(arr) dp = [0]*(n+1) for i in range(n-1, -1, -1): curMax = 0 for j in range(min(k, n-i)): curMax = max(curMax, arr[i+j]) dp[i] = max(dp[i], curMax*(j+1) + dp[i+j+1]) return dp[0] # Step 1: Memoize n = len(arr) memo = {} def dfs(i): if i in memo: return memo[i] if i == n: return 0 curMax = largest = 0 for j in range(min(k, n-i)): curMax = max(curMax, arr[i+j]) largest = max(largest, curMax*(j+1) + dfs(i+j+1)) memo[i] = largest return largest return dfs(0)

[@NeetCodeIO]

Yeah, your tabulation solution is definitely more simple, but it has little to do with the order we traverse the array. The main complexity in my solution came from the circular array memory optimization.

[@kareemadesola6522]

​@@NeetCodeIO,I find tabulating from N - 1 rather than from 0 more intuitive and natural. Starting from N - 1 when building the table feels closer to converting a recursive solution to dynamic programming. It aligns well with the way we often express recursive solutions, like return dfs(0) becoming dp[0]. This approach seems more straightforward and aids in understanding the transition from a recursive approach to dynamic programming. Could you please continue tabulating from N - 1 in your future videos as you did initially? Thanks PS: Great work giving us both approaches

[@CS_n00b]

why not just dp[abs((j - 1)%k)] instead of dp[(j - 1)%k] if j > 0 else dp[-1]

[@karananeja8054]

how is 9 + 10 = 15?

[@Marcox385]

Well, there goes my 2 day streak