[LeetCode]410. 分割数组的最大值（Split Array Largest Sum）

题目描述

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

示例:

输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

解题思路

二分法。目标值一定是在数组的最大值和数组和之间的，对这个区间进行二分。
二分思路：对当前的最大和，模拟子数组的生成过程，每个子数组都选到最接近最大和，最后看分到的子数组的数量来决定使用哪一边的区间。若子数组数量大于 m，则说明最大和取得太小了，反之。

代码

Python 3.6

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        max_num = max(nums)
        if len(nums) == m:
            return max_num
        l, r = max_num, sum(nums)
        while l < r:
            mid = (l + r) // 2
            
            # 模拟子数组的分割
            tmp_sum, count = 0, 1
            for num in nums:
                tmp_sum += num
                if tmp_sum > mid:
                    tmp_sum = num
                    count += 1
                    
            if count > m:
            # 若子数组的数量大于 m，说明最大和太小了，分割使用右边
                l = mid + 1
            else:
                r = mid
        return l

执行用时：56 ms
内存消耗：14 MB