分割数组的最大值

二 题目

给定一个非负整数数组和一个整数 m，
你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:
  1 ≤ n ≤ 1000
  1 ≤ m ≤ min(50, n)

示例:
输入:
  nums = [7,2,5,10,8]
  m = 2
输出:
  18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-array-largest-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {number}
 */
var splitArray = function(nums, m) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

动态规划：

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {number}
 */
const splitArray = (nums, m) => {
  const n = nums.length;
  const dp = Array.from(Array(n + 1), () => Array.from(Array(m + 1), () => Number.MAX_SAFE_INTEGER));
  const sub = Array.from(Array(n + 1), () => 0);
  for (let i = 0; i < n; i++) {
    sub[i + 1] = sub[i] + nums[i];
  }
  dp[0][0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= Math.min(i, m); j++) {
      for (let k = 0; k < i; k++) {
        dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sub[i] - sub[k]));
      }
    }
  }
  return dp[n][m];
};

console.log(splitArray(
  [7, 2, 5, 10, 8],
  2
));

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。