前言
leetcode每日一题上刷到的，极值问题，最优解法是个不太容易想到的二分法。
最优解法有点tricky且考察知识点蛮丰富，这里记录下。
题目
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 <= 10000 <= nums[i] <= 1061 <= m <= min(50, nums.length)
题目分析
给定数组nums和整数m，把nums分成连续的m个子数组，求某个分割方法，使得m个子数组的最大值最小。
老规矩，看到最大值问题，一般三种方法：暴力搜索，动规，贪心法。
作个弊，先看一眼数据量，数组长度10^4，这个量级暴力穷举肯定是没戏了；数组长在10^5以内，属于O(n2)勉强能过的类型。
来看看动规是不是可行。动规的本质是带重复子状态的搜索，那么我们的问题就变成了，是不是有重复的子状态？
尝试看看子状态：
问题：数组长度为n，分成m个子数组尝试子状态1dp[i]=数组长度i，分成m个子数组时，子数组sum最大值的最小值。 dp[n]能否由dp[i](i<n)推出？ 有点难。举个例子，nums=[7,2,5,10,8], m=2。 dp[2] = max(7, 2) = 2 dp[3]有两种切分，分别是[7, 2][5]和[7,5][2]，最优切分为前一种，dp[3] = 7+2=9 dp[4]有三种切分，分别是[7][2,5,10]，[7,2][5,10]，[7,2,5][10]，最有切分为第三中，dp[4]=7+2+5=14 ..... 可以看到，在这种子状态设定下，后面的状态很难由前面的状态得到，因为随着数组长度的增加，最优切分方法的每个子数组也在发生着变化，“重复的子状态”这个条件很难成立 pass尝试子状态2dp[i]=数组长度i，分成i个子数组时，子数组sum最大值的最小值。 这个也有点难。还是上面的例子，nums=[7,2,5,10,8], m=2。 dp[1]，只有一种情况，即sum([7,2,5,10,8])=32 dp[2]，有四种切分，分别是[7][2,5,10,8]，[7,2][5,10,8]，[7,2,5][10,8]和[7,2,5,10][8]，最优切分为第三种，dp[2]=10+8=18 可以看到，在这种尝试下，dp[i]也很难利用到之前状态的切分 尝试子状态3 dp[i][j]=数组长度i，分成j给子数组时，子数组sum最大值的最小值 dp[n][m]可否由dp[i][j](i<n, j<m）推出？似乎可以！ 举个例子。 nums=[7,2,5,10,8], m=2，即我们要求dp[5][2]，即前5个元素分成2个子数组时，子数组sum最大值的最小值。 下面考虑最后一个子数组有多长 最后一个子数组长度为1：数组分为[7,2,5,10]，[8]，前一部分最优分割的最大值为dp[4][1]，后一部分为[8]，故这种切分下子数组和最大值为max(dp[4][1], sum([8])，最大值=24 最后一个子数组长度为2：数组分为[7,2,5]，[10,8]，前一部分最优分割的最大值为dp[3][1]，后一部分为[8]，故这种切分下子数组和最大值为max(dp[3][1], sum([10, 8])，最大值=18 …… 因此，dp[i][j]可以由不断尝试最后一次切割的切割点，逐次比较max(dp[k][j - 1], sum(nums[k:i])得到
找到了子状态，动规解法呼之欲出。
来看看递推公式
dp[i][j] = min(max(dp[k][j – 1], sum(nums[k:i]))，其中k – 1<k<i
下面再来看看初始状态
dp[i][j]=数组长度i，分成j给子数组时，子数组sum最大值的最小值 case1：分组数=1时，不能拆分子数组，最优解为数组元素的和 即dp[i][j] = sum(n[0:n])，j=1 case2：数组长度=分组数时，分成若干个长度为1的子数组，最优解为数组元素最大值 即dp[i][j] = max(n[0:n])，i=j
解法1：动规O(n2 m)（部分超时）
按照上面的思路，不难写出动规的递归形式。
那么，这种递归形式下，时间复杂度是多少呢？
dp需要遍历的空间大小为n*m，每次求dp[i][j]，需要一层循环，计算min(max(dp[k][j – 1], sum(nums[k:i]))，其中k – 1<k<i，故整体时间复杂度为O(n2 m)
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
d = {}
# 前n个元素，切k刀
def dp(nums, n, k):
if (n, k) in d:
return d[(n, k)]
elif k == 0:
d[(n, k)] = sum(nums[:n])
return d[(n, k)]
elif n == k + 1:
d[(n, k)] = max(nums[:n])
return d[(n, k)]
ans = None
# 这一刀切在i~i+1中间
#print(n, k)
rsum = 0
for i in range(n - 2, max(0, k - 1) - 1, -1):
lsum = dp(nums, i + 1, k - 1)
rsum += nums[i + 1]
#print(n, k, i, lsum, rsum)
ans = max(lsum, rsum) if ans is None else min(ans, max(lsum, rsum))
d[(n, k)] = ans
return ans
return dp(nums, len(nums), m - 1)提交以后发现超时了，TLE在了最大的一组case上（数组长1000，m=50）。
在e5-2680v4的机器上面跑了下，耗时17s
executed in 17.0s, finished 11:51:39 2022-03-31
按经验，leetcode上大部分题时间限制最长能到10s左右，这里尝试改成递归形式提交下。
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
n = len(nums)
# int splitArray(vector<int>& nums, int m) {
sums = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
sums[i] = sums[i - 1] + nums[i - 1]
dp = [[999999999] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
for k in range(i - 1, j):
val = max(dp[i - 1][k], sums[j] - sums[k])
dp[i][j] = min(dp[i][j], val)
return dp[m][n]结果也是超时了，在自己的机器上跑一下，耗时12.9s
executed in 12.9s, finished 12:26:53 2022-03-31
比较好玩的是，这个代码用C++提交是能过的，这里贴下代码和结果。
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
vector<long> sums(n + 1);
vector<vector<long>> dp(m + 1, vector<long>(n + 1, LONG_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = i - 1; k < j; ++k) {
long val = max(dp[i - 1][k], sums[j] - sums[k]);
dp[i][j] = min(dp[i][j], val);
}
}
}
return dp[m][n];
}
};
在网上搜了搜，发现是可以用二分来解的，感觉蛮有意思，这里也贴一下。
解法2：
对于长度为n的数组，切分数量为k 我们知道 k=1时，数组不用切分，此时最大子数组和为sum(nums) k=n时，数组将切分为长度为1的n个子数组，此时，最大子数组的和为max(nums) 显然，对于k=m(1<=m<=k)，最小的最大子数组的和ans满足max(nums)<=ans<=sum(nums) 并且，对于任意的ans'<ans，nums都不能分割成m个子数组，使得每个子数组的和小于ans'；且对于任意的ans'>=ans，nums都可以分割成m个子数组，使得每个子数组的和小于num'。 这里可能不太直观，请仔细想一下。 举个例子：nums=[7,2,5,10,8], m=2
看起来，我们可以使用二分法求ans 那么，对于如何求对于 可以使用贪心法。 对于任意一个阈值t，我们都可以用贪心法，以O(n)的复杂度求得，nums是否可以分割成m个子数组，使得每个子数组的和不大于t。
这里贴下完整代码。
class Solution(object):
def splitArray(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
def can_split(nums, max_sum, m):
s = 0
p = 0
while p < len(nums):
if s + nums[p] > max_sum:
m -= 1
if m <= 0:
return False
s = nums[p]
else:
s += nums[p]
p += 1
return True
l = max(nums)
r = sum(nums)
while l <= r:
mid = (l + r) // 2
if can_split(nums, mid, m):
r = mid - 1
else:
l = mid + 1
return l提交上去，ac，收工！
——此处是内容的分割线——
除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接
本文链接：https://www.utopiafar.com/2022/03/31/leetcode-410-split-array-largest-sum/
码字不易，如果觉得内容有帮助，欢迎留言or点赞！