Maximum Sum of 3 Non-Overlapping Intervals


  • 1

    Click here to see the full article post


  • 0
    L

    Excellent tutorial, good job, awice!


  • 0
    S

    what if you are asked to get m subarrays instead of 3 ? Then this solution is not general enough.


  • 0
    S

    but anyway for the case of 3, it's an excellent and efficient solution


  • 0
    S

    W[i] >= W[best]: for right and W[i] > W[best]: for left, could you please explain why?


  • 0
    M

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


  • 0
    A

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.