Maximum Sum of 3 Non-Overlapping Subarrays - Leetcode 689 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
6:02 - Coding Brute Force
7:00 - Drawing Explanation
13:53 - Coding Memoization

leetcode 689

#neetcode #leetcode #python

[JamesBond-mqpd]

I studied the problem. I will try to solve it again in 6 hours.

[soumyajitganguly]

"dynamic programming is just a big fat cache" - have been waiting for this. Thanks for all the good work in 2024.

[shashwatsingh]

The while loop was the best, figured out the main dp function but couldn't understand how to cache the indices.

[Sanjay-xqxr]

Excellent explanation 🎉, Keep doing this

[tejas]

That was so amazing thanks for the solution.

[gabrielfonseca]

Bottom-up solution:

1. Initialize an array DP of size 4 * (Len(nums) + 1)
The row index represents the number of arrays currently added (i.e. counts) (0, 1, 2 or 3)
The columns represent the current location in nums
2. Initialize an array Backtrack of size DP
This is an array of pointers that indicates what was the optimal decision made at each step
3. Let DP[0][0] = 0 (Base case) and all other values be -int
4. Set all DP[I][j] = max(DP[i][j - 1], DP[i - 1][j - k])
This is the max("skip", "include")
If the index is out of bounds, assume that value is -inf
If "skip" >= "include", set the backtrack pointer at [I][j] to "skip" (prioritize skip, since that means an earlier subarray had the same value)
Otherwise, set the backtrack pointer to "include"
5. Initialize res array of size 3. Starting from the bottom-right in the backtrack array:
If the current pointer is "skip", set the index to (i, j - 1)
If the current pointer is "include", set index to (i - 1, j - k) and set res[i - 1] to j - k
6. Return result

[yhbarve]

You know what that is? Simply lovely! I'll tell you that.

[stark.]

We can do this with Sliding window, with O(1) space complexity and O(n+k) time complexity
It is also there in Editorial solutions

[leetprep]

For the code at 7:00, why do we need this "or i >= len(nums) - 1"

[buckwheatplate]

I'm going to cache that video in my watch later playlist

[thebearguym]

problems like these make me feel dumb and makes lc more fun

[pastori]

polished brute force am just playing good video

[astroversace]

what is the medium problem that he is referring to?

[yahyamohamoud]

can you add a feature to reset course progress so i cant see my old solutions

[Avi_Bedi]

can u please tell the question number of the leetcode medium u were talking?

[chaitanyayeole]

Can you make a vide on Leetcode #1001? It is a Hard question.

[kushagrabansal]

How are you seeing the old UI?!! It's disabled now for most I guess

[atulgupta]

"Nothing too crazy" Are you kidding me?

[uppubhai]

What software you use in mac to draw all these ?

[ceciljoel]

How much time it took for neatcode to first solve this problem?