410. Split Array Largest Sum

source: https://leetcode.com/problems/split-array-largest-sum/

Question

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

思路

这一题思路比较难找，但是其实是1011题的另一种表达方式：

• nums是要运送货物的列表
• m运送要求的天数
• 子数组和的最大值，其实就是载荷
• 最小值其实就是二分查找的左边界

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {number}
 */
var splitArray = function (nums, m) {
    const getMLength = (nums, payload) => {
        let total = 0;
        let leftPayload = payload;
        for (let i = 0; i < nums.length; i++) {
            const crrLeftPayload = leftPayload - nums[i];
            if (crrLeftPayload < 0) {
                total += 1;
                leftPayload = payload - nums[i];
            } else {
                leftPayload = crrLeftPayload;
            }
        }
        total += 1;
        return total;
    };
    let left = Math.max(...nums);
    let right = nums.reduce((acc, crr) => acc + crr, 0);
    while (left <= right) {
        const mid = ~~((left + right) / 2);
        const total = getMLength(nums, mid);
        if (total === m) right = mid - 1;
        else if (total > m) left = mid + 1;
        else right = mid - 1;
    }
    return left;
};

End

对于题目要有举一反三的能力，没有的话就只能记忆一下了。