泰州专一做淘宝网站,奉化市建设局网站,做qq链接的网站,如何把网站提交到百度hard:https://leetcode.cn/problems/split-array-largest-sum/ 给定一个非负整数数组 nums 和一个整数 m #xff0c;你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1#xff1a;输入#xff1a;nums [7,2,5,1… hard:https://leetcode.cn/problems/split-array-largest-sum/ 给定一个非负整数数组 nums 和一个整数 m 你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1输入nums [7,2,5,10,8], m 2
输出18
解释
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18在所有情况中最小。
示例 2输入nums [1,2,3,4,5], m 2
输出9
示例 3输入nums [1,4,4], m 3
输出4提示1 nums.length 1000
0 nums[i] 106
1 m min(50, nums.length)题解 令 dp[i][j]表示将数组的前 i 个数分割为 j 组所能得到的最大连续子数组和的最小值 确定装填转移方程(考虑dp[i][j]需要遍历所有分为j-1组的情况) d p [ i ] [ j ] m i n k 0 i − 1 { m a x ( d p [ k ] [ j − 1 ] , s u b ( k 1 , i ) ) } m i n k 0 i − 1 { m a x ( d p [ k ] [ j − 1 ] , s u m ( n u m s [ k 1 … j ] ) ) } dp[i][j] min_{k0}^{ i−1} \{max(dp[k][j−1],sub(k1,i))\}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ min_{k0}^{ i−1} \{max(dp[k][j−1],sum(nums[k1…j]))\} dp[i][j]mink0i−1{max(dp[k][j−1],sub(k1,i))} mink0i−1{max(dp[k][j−1],sum(nums[k1…j]))} 确定边界填表法 nums [7,2,5,10,8]m2。
i\j0120无法分为0组INT_MAXINT_MAX1无法分为0组71个数无法分为2组ij2无法分为0组72 m i n ( [ 7 ] , [ 2 ] ) 2 min([7],[2])2 min([7],[2])23无法分为0组725 m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 ] ) ] 7 min\begin{bmatrix} max(dp[1][1],[2,5]) \\ max(dp[2][1],[5]) \end{bmatrix}7 min[max(dp[1][1],[2,5])max(dp[2][1],[5])]74无法分为0组72510 m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 , 10 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 , 10 ] ) m a x ( d p [ 3 ] [ 1 ] , [ 10 ] ) ] 14 min\begin{bmatrix} max(dp[1][1],[2,5,10]) \\ max(dp[2][1],[5,10]) \\ max(dp[3][1],[10]) \end{bmatrix}14 min max(dp[1][1],[2,5,10])max(dp[2][1],[5,10])max(dp[3][1],[10]) 14 前*个数分为一组和剩下的部分5无法分为0组725108 m i n [ m a x ( d p [ 1 ] [ 1 ] , [ 2 , 5 , 10 , 8 ] ) m a x ( d p [ 2 ] [ 1 ] , [ 5 , 10 , 8 ] ) m a x ( d p [ 3 ] [ 1 ] , [ 10 , 8 ] ) m a x ( d p [ 4 ] [ 1 ] , [ 8 ] ) ] 18 min\begin{bmatrix} max(dp[1][1],[2,5,10,8]) \\ max(dp[2][1],[5,10,8]) \\ max(dp[3][1],[10,8])\\ max(dp[4][1],[8]) \end{bmatrix}18 min max(dp[1][1],[2,5,10,8])max(dp[2][1],[5,10,8])max(dp[3][1],[10,8])max(dp[4][1],[8]) 18
code
class Solution {
public:int splitArray(vectorint nums, int m) {int n nums.size();vectorvectorlong long dp(n 1, vectorlong long(m 1, LLONG_MAX));vectorlong long sub(n 1, 0);for (int i 0; i n; i) {sub[i 1] sub[i] nums[i];}dp[0][0] 0;for (int i 1; i n; i) {for (int j 1; j min(i, m); j) {for (int k 0; k i; k) {dp[i][j] min(dp[i][j], max(dp[k][j - 1], sub[i] - sub[k]));}}}return (int)dp[n][m];}
};
