题目分析

这个题目非常有难度，要将一个数组拆分成若干个子数组，并且要求得到的各个子数组之和的最大值最小。也就是说我们要切割的非常巧妙，尽量让每一个子数组之和相同，这样就不会产生有的很大，有的很小的问题。

动态规划

我们假定f[i][j]代表前i个元素分成j个数组，得到的最优解。而且已知cum_sum为前缀和，前缀和就是前i个数字的总和。如cum_sum[i] = nums[0] + nums[1] + … + nums[i - 1]，当i=0时，cum_sum=0。那么我们可以得出状态转移方程f[i][j] = min(f[i][j], max(f[k][j-1], cum_sum[i] - cum_sum[k])) for k in range(i - 1)。具体描述一下，f[k][j-1]说明的是在从前i个数分成j个数组中，已经将前k个数分成了j-1个数组得到的最优解，然后其余的从第k+1个数到第i个数之和为cum_sum[i] - cum_sum[k]，然后求两者的最大值，为这次分割得到的子数组最大值。遍历所有的k，求得使这个最大值最小的值。因为对于每一个数组前缀i和子数组个数j都要遍历i次，求出f[i][j]的最优解。因此时间复杂度为$O(n^{2}m)$，空间复杂度为$O(nm)$，其中n为数组的长度，m为子数组的个数。

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        cum_sum = [0]
        n = len(nums)
        for i in range(n):
            cum_sum.append(cum_sum[-1] + nums[i])
        
        dp = [[float('inf') for _ in range(m + 1)] for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(i, m) + 1):
                for k in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[k][j - 1], cum_sum[i] - cum_sum[k]))
        return dp[-1][-1]

二分查找+贪心

这道题最妙的地方不在于DP，而是二分查找+贪心的算法，官方题解中写道：「使……最大值尽可能小」是二分搜索题目常见的问法。我们已知子数组之和的上限和下限，要找到最小的满足条件的子数组之和，就可以采用二分法，让上限和下限逐渐逼近于最终的答案。因为这是一个连续的子数组之和问题，所以我们只需要选择一个值，然后让子数组之和尽可能接近这个值，但是不超过这个值，一但超过，说明进入了下一个子数组。如果到最后子数组的个数小于等于给定的子数组个数，则说明这个值是满足条件的，可能需要继续缩小。否则这个值是小的，应该继续增大。
**因为子数组的最大值为全部数字之和，记作sum，子数组的最小值为单个数字的最大值，记作max，当然还可以继续优化，可以选择max和sum整除m的较大者。因为sum平分成m份，至少每个数组之和都是sum除以m，因此至少为sum整除m，我们就按照官方题解来叙述。从sum和max之间进行二分查找。因此时间复杂度为$O(nlog(sum-max))$，空间复杂度为$O(1)$**。

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:

        def check(max_val):
            current_sum = 0
            current_group = 1
            for x in nums:
                current_sum += x
                if current_sum > max_val:
                    current_group += 1
                    current_sum = x
                    if current_group > m:
                        return False
            return True

        left, right = max(nums), sum(nums)
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

刷题总结

这道题目非常有趣，我们在学习或者使用二分的时候，都觉得没什么难度。但是这个题目，巧妙的利用了二分查找的特点，是二分查找的进阶应用，小伙伴们一定要灵活使用它。