[leetcode] 410. Split Array Largest Sum

Description

Given an array 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.

Note:
If n is the length of array, assume the following constraints are satisfied:

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

Examples:

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.

分析

题目的意思是:把一个数组分为m个子数组,使得子数组的最大值最小。

  • 如果将整个数组看为一个整体,那么最少有1组,所以i的范围是[1, j],所以要遍历这中间所有的情况,假如中间任意一个位置k,dp[i-1][k]表示数组中前k个数字分成i-1组所能得到的最小的各个子数组中最大值,而sums[j]-sums[k]就是后面的数字之和,我们取二者之间的较大值,然后和dp[i][j]原有值进行对比,更新dp[i][j]为二者之中的较小值,

  • 这样k在[1, j]的范围内扫过一遍,dp[i][j]就能更新到最小值,我们最终返回dp[m][n]即可

代码

class Solution {
    
public:
    int splitArray(vector<int>& nums, int m) {
        int n=nums.size();
        vector<int> sums(n+1,0);
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_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++){
                    int val=max(dp[i-1][k],sums[j]-sums[k]);
                    dp[i][j]=min(dp[i][j],val);
                }
            }
        }
        return dp[m][n];
    }
};

参考文献

[LeetCode] Split Array Largest Sum 分割数组的最大值

上一篇:Leetcode-1031 Maximum Sum of Two Non-Overlapping Subarrays(两个非重叠子数组的最大和)


下一篇:[Swift]LeetCode795. 区间子数组个数 | Number of Subarrays with Bounded Maximum