@@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.
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.
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.
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 :)
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?
@@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?
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)
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.
@@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
10 + 9 = 15 caught me so off guard 😭 take a rest bro
great video tho
Solved this by myself!!
Love to hear it!!
@@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.
No😢
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.
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.
you stared this question .this problem is some what different and great
Thank you for providing multiple solutions!!
I am happy because I was able to come up with recursive solution with memorization on my own.
Thank you !!
Thank you so much
phew, they really do want us preoccupied during the weekends
Even though I know it's a dp problem, I still struggle to figure it out ! Thanks for your ingenious solution as always!
Thanks❤
back with another video
Amazing
Kind Request : Please explain leetcode 1190 it is not in neetcode it is asked in our campus placement drive !
i do my dp solution both ways for better understanding..
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.
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.
1:24 9+10 = 15 🤣
what is difference between this and sliding window maximum
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 :)
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?
To get subarrays unfortunately you cant reorder the elements
@@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?
I think the order of elements matter. Consider this example:
arr = [10, 10, 1, 1, 1, 1], k = 3.
At 7:20 time complexity of brute force should be O(N^k)
1:25 I was out here thinking 9+10=21 but it turns out it's 15
why not just dp[abs((j - 1)%k)] instead of dp[(j - 1)%k] if j > 0 else dp[-1]
Neato! Brain Fried 🤯
1:22 What?
Omfg, if my parents saw that they would bring out the chappal 🥿
@@NeetCodeIO bhai what is this hera pheri xD
what in the indian trauma is this@@NeetCodeIO
how is 9 + 10 = 15?
Well, there goes my 2 day streak
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)
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.
@@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
Chimp