Split Array Largest Sum


  • 1
    T

    Click here to see the full article post


  • 0
    L

    @tinylic I think the Time complexity for binary search approach should be O(n * log(sum_of_array) ) ?


  • 1
    T

    @LeonCheng yes you are right. I will fix it later. Thank you!


  • 0

    Hi, why does the recursive solution have the check: if (i > 0)? Isn't this hit only when overflow occurs and the integer wraps around? Since n is 1000, I don't understand why this check is needed. Thanks, Clayton


  • 1
    T

    @claytonjwong Hi clayton, thank you for your question. This branch is mainly used to consider the first element and other elements seperately. For an ordinary element, we have two choices: append it to the previous subarray or start a new subarray. But for the first element, there is no existing "previous subarray", so we only have one choice.
    Best,
    tinylic


  • 0

    @tinylic thanks, wow I initially completely misread this simple statement as i < 0. Oops. thanks!!


  • 0
    W

    I don't understand the intuition for this algorithm. Could somebody explain it to me? I understand that the largest possible answer is when m = 1, which correspond to sum(nums). I also get that the smallest possible answer is when m = n, which corresponds to max(nums). I also understand that you can do binary search between these numbers to find the minimum maximum sub-array sum.

    However, I don't understand why you need to count the number of sub-arrays for a given midpoint value. I understand that if it goes above m, then mid is too small a number and you're too close to m=n. But what about count is less than m? How come we don't ever need to explicitly check that our answer corresponds to m? How does the midpoint end up converging to the actual minimum maximum subarray for a value m? It seems almost agnostic to m?

    Thanks for the help!


  • 0
    W

    Question #2: I also don't understand why mid, a value that is never explicitly constrained to be a sum of the subarrays, will correspond to the sum of the subarrays. Thanks!


  • 0
    T

    @wcarvalho Hi wcarvalho, thanks for your question. If I get your point correctly, your first problem is: For a given midpoint value, if the number of subarrays is less than m, why don't we check whether we can divide the array into exact m subarrays?
    Well, that's a good question. First, the property "all elements are non-negative" is very useful. It means if we split a subarray into several smaller subarrays, the maximum sum of subarrays will not increase. Thus, for a given midpoint value, if the counter of subarrays is less than m with regard to the maximum sum of subarrays not exceeding mid, then by splitting subarrays into smaller subarrays, we can always find a strategy to split the array into EXACT m valid subarrays.

    For the second problem, indeed, there is no constraint that mid should be a sum of subarrays. Using binary search, mid will finally converge to a very point that our F function turns to true for the first time. This point can be proved to always be a sum of subarrays, so the mid will finally converge into a sum of subarrays.

    Hope it helps,
    tinylic


  • 0
    R

    If we were dealing with an array of doubles and wanted an exact answer, I'm guessing approach 3 would not work at all?


  • 0
    R

    If we were dealing with an array of doubles and wanted an exact answer, I'm guessing approach 3 would not work at all?


  • 0
    T

    @rainmaker9001 It still works. We can get the answer in a given error range.


  • 0
    S

    The java code in approach 2: Dynamic programming has one minor problem, it won't pass a test case: [7,2,5,10,8] 10, which m is larger than num's length. But we can take it as a special case.


  • 0
    T

    @shminjs m should not be larger than n. It is mentioned in the description.


Log in to reply
 

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