410.split-array-largest-sum.md

410. Split Array Largest Sum

nums = [7, 2, 5, 10, 8]
k = 2

[7, 2, 5, 10, 8]
 7| 2, 5, 10, 8 = max(7, 25) = 25
 7, 2| 5, 10, 8 = max(9, 23) = 23
 7, 2, 5| 10, 8 = max(14, 18) = 18 // the minimum of largest sum
 7, 2, 5, 10| 8 = max(24, 8) = 24

Binary Search

We try to minimize the largest sum amoung k subarrays:

• Lower bound is max(nums), because we can split the array into k == n subarrays which is [7 | 2 | 5 | 10 | 8] = 10.
• Upper bound is sum(nums), because we can split the array into k == 1 subarray (only one split) which is [7 + 2 + 5 + 10 + 8] = 32. The possible answer must be in the range [max(nums), sum(nums)].

Since we have a fixed search space, then we have to discover the monotonicity characteristic to apply binary search:

• Given a largest sum ans (answer), if we can split the array into k groups, then we also can split the array with larger value ans + 1, ans + 2, etc. Because there are more numbers formed one split with the larger value, the total split count will become less, which also satisfy the condition: splitCount <= k. (Why splitCount < k is also acceptable? See below)
• If the largest sum is too small that we can't split the array into k groups (more than k splits), then we also can't split the array with smaller largest sum since smaller value will have more splits.

This is the monotonicity characteristic, we can apply binary search to find the answer.

在一個搜尋範圍內，利用單調性去逼近這個答案。我們需要先挖掘單調性。

「元素和的最大值」越小，划分出的段数就越多，反之越少。

nums = [7, 2, 5, 10, 8]
k = 3

x = 14
7, 2, 5 | 10 | 8 // split count = 3 <= k, valid
...
x = 25
7, 2, 5, 10 | 8 // split count = 2 <= k, valid

x = 13
7, 2 | 5 | 10 | 8 // split count = 4 > k, invalid
...
x = 10
7, 2 | 5 | 10 | 8 // split count = 4 > k, invalid

Why Allowing splitCount < k?

Given the middle (binary search on answer), and we check if all splits that the sum of all splits are <= middle. While splitCount < k is acceptable because we can keep splitting one of the subarrays into more subarrays which largest sum is still <= middle that satisfies the condition as well. (The more split we have, the less sum we have in each split, that keeps sastifying the largest sum <= middle)

分割數不夠，就再分割，而且再分割後的最大和也不會超過原本的最大和。 [5,6][7,8], split = 2, max(11, 15) = 15 -> [5][6][7][8], split = 4, max(5, 6, 7, 8) = 8

當最大值越大，單一分割可以容納更多數字，使得分割數越少，越可以滿足 splitCount <= k

k = 4
middle = 12
[1, 2, 3, 4, 5]
 ^^^^^^^^^^  ^
[1, 2, 3, 4][5]
     10      5  < 12
splitCount = 2 <= k

// We keep splitting
[1, 2, 3][4][5]
    6     4  5  < 12
splitCount = 3 <= k

// We keep splitting
[1, 2][3][4][5]
  3    3  4  5  < 12
splitCount = 4 <= k, satisfied

Keywords to apply binary search from problem description: 非空、連續、非負整數陣列、最大化最小值

fun splitArray(nums: IntArray, k: Int): Int {0
    var left = 0
    var right = 0
    for (n in nums) {
        left = maxOf(left, n)
        right += n
    }

    while (left <= right) {
        val middle = left + (right - left) / 2
        if (splitCount(nums, middle) <= k) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

/**
 * Given a value, check how many subarray we can split the input array into so that
 * the sum of each subarray <= value.
 * Check first, add later.
 */
private fun splitCount(nums: IntArray, value: Int): Int {
    var split = 1
    var sum = 0
    for (n in nums) {
        if (sum + n > value) {
            split++
            sum = 0
        }
        sum += n
    }
    return split
}

// Or equivalently: add first, check later
private fun splitCount(nums: IntArray, value: Int): Int {
    var split = 1
    var sum = 0
    for (n in nums) {
        sum += n
        if (sum > value) {
            split++
            sum = n
        }
    }
    return split
}

/**
 * Or equivalently, straightforward way, we iterate directly to to sum the subarray and check the sum <= value.
 */
fun canSplit(nums: IntArray, k: Int, value: Int): Boolean {
    // [A, B, C, D]
    // A + B <= value
    // A + B + C > value
    // A + B | C, D

    // check how many subarray which sum <= value == k?
    var split = 0
    var i = 0
    while (i < nums.size) {
        var j = i
        var sum = 0
        while (j < nums.size && sum + nums[j] <= value) {
            sum += nums[j]
            j++
        }
        split++
        i = j
    }
    return split <= k
}

Dynamic Programming

TODO