【leetcode】410. Split Array Largest Sum分割数组的最大值


前言

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 <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= m <= min(50, nums.length)

题目分析

给定数组nums和整数m,把nums分成连续的m个子数组,求某个分割方法,使得m个子数组的最大值最小。

老规矩,看到最大值问题,一般三种方法:暴力搜索,动规,贪心法。

作个弊,先看一眼数据量,数组长度10^4,这个量级暴力穷举肯定是没戏了;数组长在10^5以内,属于O(n2)勉强能过的类型。

来看看动规是不是可行。动规的本质是带重复子状态的搜索,那么我们的问题就变成了,是不是有重复的子状态?

尝试看看子状态:

问题:数组长度为n,分成m个子数组
尝试子状态1
dp[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

尝试子状态2
dp[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点赞!


发表回复

您的电子邮箱地址不会被公开。