410. Split Array Largest Sum

410. Split Array Largest Sum

题目链接：https://leetcode.com/problems...

枚举所有可能的largest sum，找最小的那个，二分枚举优化复杂度，因为数组不含负数，根据largest sum是否满足条件可以二分结果。largest sum的范围是(sum(nums)/m, sum(nums))，找当前largest sum是否存在，判断存在的标准是：扫一遍array，看实现每个subarray的sum都<=当前largest sum的时候subarray的数量是否小于等于mm，注意求数组sum要用long，防止溢出。

public class Solution {
    public int splitArray(int[] nums, int m) {
        long sum = 0;
        for(int num : nums) sum += num;
        // binary search, find the minimum valid sum
        long l = sum / m;
        long r = sum;
        while(l < r) {
            long mid = l + (r - l) / 2;
            boolean valid = isValidSplit(nums, m, mid);
            if(valid) r = mid;
            else l = mid + 1;
        }
        
        return (int) l;
    }
    
    private boolean isValidSplit(int[] nums, int m, long sum) {
        int i = 0, n = nums.length;
        // count the minimum number of split
        int count = 0;
        // prev sum
        long prev = 0;
        // loop invariant: prev = 0, count = minimum splits so far
        while(i < n) {
            if(nums[i] > sum) return false;
            while(i < n && prev + nums[i] <= sum) {
                prev += nums[i++];
            }
            count++;
            if(count > m) return false;
            prev = 0;
        }
        
        return count <= m;
    }
}

还有一种dp的做法：
https://discuss.leetcode.com/...

dp的subproblem是：
dp[i][j]: split nums[0:i] into j parts,
dp的方程是：
dp[i][j] = min{ max{dp[k][j-1], sum(nums[k+1:i+1])} },
每个subproblem都遍历一遍可能的k，选择出最小的结果。注意由于array不含负数，dp[k-1] <= dp[k] 并且sum(nums[k:i+1]) >= sum(nums[k+1:i+1])，相当于一条递增，一条递减的线找交点，极端情况没有交点结果出现在两端，所以依然可以binary search找dp[k] == sum(nums[k+1:i+1])。