410. Split Array Largest Sum

[Tcdian]

410. Split Array Largest Sum

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

Example

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.

Note

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

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {number}
 */
var splitArray = function(nums, m) {
    const len = nums.length;
    const sub = new Array(len);
    sub[0] = nums[0];
    for (let i = 1; i < len; i++) {
        sub[i] = sub[i - 1] + nums[i];
    }
    const dp = Array.from(new Array(len), () => new Array(m + 1).fill(Infinity));
    for (let i = 0; i < len; i++) {
        for (let j = 1; j <= Math.min(i + 1, m); j++) {
            if (j === 1) {
                dp[i][j] = sub[i];
            } else {
                for (let k = 0; k <= i; k++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(sub[i] - sub[k], dp[k][j - 1]));
                }
            }
        }
    }
    return dp[len - 1][m];
};

• TypeScript Solution

function splitArray(nums: number[], m: number): number {
    const len = nums.length;
    const sub: number[] = new Array(len);
    sub[0] = nums[0];
    for (let i = 1; i < len; i++) {
        sub[i] = sub[i - 1] + nums[i];
    }
    const dp: number[][] = Array.from(new Array(len), () => new Array(m + 1).fill(Infinity));
    for (let i = 0; i < len; i++) {
        for (let j = 1; j <= Math.min(i + 1, m); j++) {
            if (j === 1) {
                dp[i][j] = sub[i];
            } else {
                for (let k = 0; k <= i; k++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(sub[i] - sub[k], dp[k][j - 1]));
                }
            }
        }
    }
    return dp[len - 1][m];
};