410. Split Array Largest Sum (Hard).md

410. Split Array Largest Sum (Hard)

https://leetcode.com/problems/split-array-largest-sum/

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= m <= min(50, nums.length)

思路

• 记忆化递归（最后一个test case会超时）
• 二分 + 贪心。因为我们最后的答案是要得到数组中划分m个区间的min sum，那么可以转化为一个二分搜索问题，left = 0， right = sum(nums)，求解mid，使得划分k个区间满足 k<=m。那么，问题转化为给定一个数字(mid)，求以该数字作为总和上限时，能分成多少个区间，这个过程是贪心的思想，因为数组为非负，我们可以从左往右扫描并求和，如果每次加进来的数字不超过mid，那么就不需要增加区间k++, 直到加的数字超过mid，再k++. 我们发现的规律是，每次给的mid越小，数组分割的区间就会越多，反之亦然。

代码

class Solution:
    def splitArray(self, A: List[int], m: int) -> int:
        # Greedy + binary search
        return splitArray(A, m)

def check(A, m, mid):
    ssum, k = 0, 0
    for x in A:
        if x > mid:
            return False
        if ssum + x > mid:
            k += 1
            ssum = x
        else:
            ssum += x
    if ssum > 0:
        k += 1
    return k <= m
        
def splitArray(A, m):
    left, right = 0, sum(A) + 1
    while left < right:
        mid = left + (right - left) // 2
        if check(A, m, mid):
            right = mid
        else:
            left = mid + 1
    return right