https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/ I’m trying to figure out dp approach but do not have slightest idea where to start. Any leetcode experts can guide me on how do you approach these kind of questions? I have a feeling that i will be asked this question on fb onsite.
Looks like a pretty standard dp question.
Check the discussions
Pretty stupid question for an interview btw
All DP questions are stupid tbh
It's a DP problem. First create an array of ints. Each index will represent the sum of the sub array from current index to curr index+ subarray size. Have a set as a way to check if this index was used in the result. Then for loop this DP array to find largest int, update set as you go. Could use a while loop so you can do some optimization and skip indexes. Could further optimize by sorting the DP while keeping the index entry in each index as well.
It's not that hard of a question, make sure you understand it.
I solved this question during the weekend when someone posted it here. The key point for me was the mention of the number 3 and the variable k. This problem combines the use of left/right arrays (DP), prefix sums and sliding windows. Since it mentioned a subarray of size k, sliding windows immediately came to mind. The other thing with a lot of array problems (especially the trickier ones) is that they rely on some sort of left (0 to n) and right (n to 0) arrays and that was the case in this one as well. My approach was basically this: 1. For left_max: Maintain a sliding window of size k starting from 0 and ending at n. This could end at n - 2*k too but I made it go till n 2. For right_max: Maintain a sliding window of size k starting from 2*k and ending at n For me, the elements of the left_max and right_max arrays were a class like so: class ArraySumWithStartIndex attr_accessor :sum, :start_index end The reason for those left_max and right_max arrays is that we will maintain a middle window of size k when traversing through the array at the end For the middle window, once we hit the index k, we can start comparing the sum of [left_sum + middle_sum + right_sum] and setting the result based on that Tried out a couple test cases before submission in order to get the array indices correct.
Thanks for your detail approach. Array/subarray/string manipulation questions usually trip me which require 2 pointers/sliding windows/presum caching etc. I cant seem to use those technique properly on never seen questions. Do you have any tips how to get better at those?
+1
What are you then?
I think this can be solved in O(n) time with O(n) space complexity. Idea is to traverse the array thrice: 1. First pass: maintain a max subarray list.(going from k-1 to n) 2. Second pass: maintain a max 2 subarray sum list. This can be done by using the previous array and summing up the max subarray sum at i with the subarray sum at I+k. This way, you get 2 subarrays with max sum. 3. Third pass: use the same trick from step 2 to get 3 subarray with max sum. Solved this in the loo. Truly the place for great thinking :p
Great thinking happens on the pot. 👍
(God damn it).