Click here to see the full article post
what if you are asked to get m subarrays instead of 3 ? Then this solution is not general enough.
W[i] >= W[best]: for right and W[i] > W[best]: for left, could you please explain why?
As given in the example
Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
We also have a subarray [6,7] ; why is it not being considered ? Is it because of the "non-overlapping" criteria? They just touch each other [2,6], [6,7], [7,5] and sums to (8, 13, 12)
Can anyone please explain ???
There is a better way to do this that also works for any number of intervals. It's similar to the described approach, but "j" is not special and the scans are in the same direction.
@sha256pki This is done to get lexicographically smallest output, in the 'right' array we need the left-most maximum sum available.
@mondal.r They need to be non-overlapping
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.