Maximum Sum of 3 Non-Overlapping Intervals


  • 0

    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.


  • 0
    B

    Not the best solution but it works.


  • 0
    N

    @sha256pki This is done to get lexicographically smallest output, in the 'right' array we need the left-most maximum sum available.


  • 0
    N

    @mondal.r They need to be non-overlapping


  • 0
    J

    This solution can not ensure that right[i] is the the lexicographically smallest one, if there are multiple subarraies on the right giving the same sum.


Log in to reply
 

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