Partition Array for Maximum Sum - Leetcode 1043 - Python

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

[pastori]

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

[saminhasan]

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.

[SanketBhat]

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

[kareemadesola]

phew, they really do want us preoccupied during the weekends

[yaswanthkosuru]

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

[LokendraSingh-]

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

[rorothepropro]

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

[tranminhquang]

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

[anlee]

Thank you for providing multiple solutions!!

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

[user-yt]

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

[EmenikeAnigbogu]

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

[vikneshcs]

Can the number of partitions exceed k here

[CS_nb]

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

[midhileshmomidi]

what is difference between this and sliding window maximum

[ayush]

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?