Split Array Largest Sum


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


@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

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

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 subarray sum.
However, I don't understand why you need to count the number of subarrays 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!

@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 nonnegative" 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

