LeetCode之Split Array Largest Sum

问题：

方法：
贪心算法加二分查找，正确结果必在（0，sum(nums)）中，通过计算mid逐渐逼近到正确结果。

具体实现：

class SplitArrayLargestSum {
    fun splitArray(nums: IntArray, m: Int): Int {
        var left = 0
        var right = nums.sum() + 1
        var ans = Int.MAX_VALUE
        while (left < right) {
            val mid = (left + right) / 2
            if (guess(nums, m, mid)) {
                ans = mid
                right = mid
            } else {
                left = mid + 1
            }
        }
        return ans
    }

    private fun guess(nums: IntArray, m: Int, mid: Int): Boolean {
        var sum = 0
        var innerM = m
        for (num in nums) {
            if (sum + num > mid) {
                innerM--
                sum = num
                if (num > mid) {
                    return false
                }
            } else {
                sum += num
            }
        }
        return innerM >= 1
    }
}

fun main(args: Array<String>) {
    val input = intArrayOf(2, 8)
    val m = 1
    val splitArrayLargestSum = SplitArrayLargestSum()
    println(splitArrayLargestSum.splitArray(input, m))
}

有问题随时沟通

具体代码实现可以参考Github