[leetcode] 410. Split Array Largest Sum

[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 ≤ 10001 ≤ 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& nums, int m) { int n=nums.size(); vector sums(n+1,0); vector> dp(m+1,vector(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

参考文献

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。