410. 分割数组的最大值 (opens new window)

1.二分

思路：最大最小问题&最小最大问题直观思路考虑二分法。

二分的对象为分割数组的最小最大值，即为所求。此处单调性的必要性在于，若存在一种分割方法，使当前数组分割后的最大子数组和为sum，那么大于sum的分割方法一定存在，而小于sum的分割方法不一定存在。

每次通过二分法枚举子数组和最大值mid，如果判断存在一种分割方法使每个子数组和小于等于mid，那么说明“最小最大值”在【left,mid】之间，否则说明当前mid过小，需要在右侧寻找。

判断是否存在某种切割方法当中，因为子数组连续，因此贪心法只要当前子数组和还没有超过mid，则不断从右侧加入新的元素。

class Solution {
    public int splitArray(int[] nums, int k) {
        int sum=0,max=0;
        for (int x : nums) {
            sum += x;
            max = Math.max(max, x);
        }
        int left = max, right = sum;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    /** 
     * 判断数组能否划分成k个子数组和都小于等于mid的子数组
     */
    private boolean check(int[] nums, int k, int mid) {
        int sum = 0, step = 0;
        for (int x : nums) {
            //装得下
            if (sum + x <= mid) {
                sum += x;
            } 
            else {
                sum = x;
                step++;
                if(sum>mid||step>=k) return false;
            }
        }
        return true;
    }
}

2.动态规划

定义dp[k][nums.length]：表示dp[m][n]第n个位置进行第m个分割时，当前得到的最小子数组和。

算法实现时，需要枚举前n-1个位置中，所有第m-1次分割的结果。基于旧的分割点计算当前子方案最大子数组和时，需要O(1)获取“任意两个位置的子数组和”(否则时间复杂度达到n的三次方)，因此开辟空间保存前缀和。

class Solution {
    public int splitArray(int[] nums, int k) {
       int[][] dp = new int[k][nums.length];
        int[] pre = new int[nums.length];
        //计算前缀和
        for (int i = 0; i < nums.length; i++) {
            if(i==0) pre[i] = nums[0];
            else pre[i] = pre[i - 1] + nums[i];
        }
        
        for (int i = 0; i < k; i++) {
            for (int m = 0; m < nums.length; m++) {
                dp[i][m] = i==0?pre[m]:Integer.MAX_VALUE;
                if(i==0) continue;
                for (int n = 0; n < m; n++) {
                    //n+1 - m之间的区间和
                    int preSum = pre[m] - pre[n];
                    int preResult = Math.max(dp[i - 1][n], preSum);
                    dp[i][m] = Math.min(dp[i][m], preResult);
                }
            }
        }
        return dp[k-1][nums.length - 1];
    }
}