分割数组的最大值

410. 分割数组的最大值

给定一个非负整数数组和一个整数 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，在所有情况中最小。

方法一：暴力（超时）

我们要将 nums[0 … n - 1] 分为 m 个非空的子数组，我们可以先将 nums 数组分为 [0 … i)，[i … n -1]两个数组(1 < i <= n - 1)，再计算 nums[i … n - 1] 分成 m - 1个子数组各自和的最大值最小，可以看出这是一个递归操作。

class Solution {
    public static int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[] count = new int[n + 1];
		//利用前缀和数组进行优化
        for(int i = 1; i <= n; i++){
            count[i] = count[i - 1] + nums[i - 1];
        }
		// num 数组最多分成 n 个子数组
        return split(count, m > n ? n : m - 1, 0, n - 1);
    }

    public static int split(int[] count, int m, int start, int end){
        //判断是否还需要切分，否则返回[start, end]范围内的元素之和
        if(m == 0){
            return count[end + 1] - count[start];
        }

        int min = Integer.MAX_VALUE;
        //枚举每一个切分位置
        for(int i = start + 1; i <= end && m > 0; i++){
            //递归地计算[i, end]分割为 m - 1个子数组的最大值的最小值
            int right = split(count, m - 1, i, end);
            //维护最小值
            min = Math.min(min, Math.max(count[i] - count[start], right));
        }
        return min;
    }
}

时间复杂度O(n^m)，空间复杂度O(n)。爆炸！！！

方法二：动态规划

令f[i][j]表示将数组的前 i 个数分割为 j 段所能得到的最大连续子数组和的最小值。我们枚举第 j 段的具体范围，我们可以枚举 k，其中前 k 个数被分割为 j - 1 段，而第 k + 1到第 i 个数为第 j 段。此时，这 j 段子数组中和的最大值就等于 f[k][j - 1]和sub(k + 1, i)中的较大值，其中sub(i, j)表示数组 nums 中下标落在区间[i, j]内的数的和。得到状态转移方程：
$$
f[i, j] = \min^{i-1}_{k=0}{max(f[k][j - 1],sub(k + 1, i))}
$$
i 个数最多只能分成 i 段，因此 i >= j 是合法状态，对于不合法的状态(j > i)，由于我们求的是最小值，我们将其初始化为一个很大的值，当我们尝试从不合法的状态转移，得到的结果将是一个很大的数。

我们还需要初始化f[0][0] = 0，最后的结果为 f[n][m]。

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] dp = new int[n + 1][m + 1];
        //将 dp 数组全部设为最大值
        for(int i = 0; i <= n; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
		//生成前缀和数组
        int[] sub = new int[n + 1];
        for(int i = 0; i < n; i++){
            sub[i + 1] = sub[i] + nums[i];
        }
		//初始状态
        dp[0][0] = 0;
        //从前往后依次计算 dp 数组的值
        for(int i = 1; i <= n; i++){
            //j <= i
            for(int j = 1; j <= Math.min(i, m); j++){
                //枚举最后一个子数组的切割点
                for(int 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];
    }

}

时间复杂度O(m*n^2)，n 为数组的长度，m 为非空连续子数组的个数。

空间复杂度O(n * m)。

方法三：二分查找

本题中，我们注意到：当我们选定一个值 x，我们可以线性地验证是否存在一种分割方案，满足其最大分割子数组和不超过 x。策略如下：

贪心地模拟分割的过程，从前到后遍历数组，用 sum 表示当前分割子数组的和，cnt 表示已经分割出的子数组的数量(包括当前子数组)，那么每当 sum 加上当前值超过了 x，我们就把当前取的值作为新的一段分割子数组的开头，并将分割出的子数组的数量 cnt 加一。遍历结束后验证是否 cnt 不超过 m。

我们可以使用二分查找来解决。二分的上界为数组 nums 中所有元素的和，下界为 nums 中所有元素的最大值。通过二分查找，我们可以得到最小的最大分割子数组和。

class Solution {
    public int splitArray(int[] nums, int m) {
        int left = 0, right = 0;
		// 初始化二分查找上下界
        for(int i = 0; i < nums.length; i++){
            right += nums[i];
            if(left < nums[i]){
                left = nums[i];
            }
        }

        while(left < right){
            int mid = left + (right - left) / 2;
            if(check(nums, mid, m)){
                right = mid; //存在最大分割子数组的和小于 x，将 x 缩小
            }else{
                left = mid + 1;//不存在最大分割子数组的和小于 x，将 x 增大
            }
        }
        return left;
    }
	//检查是否存在最大分割子数组的和 小于 x
    public boolean check(int[] nums, int x, int m){
        int sum = 0;
        int cnt = 1;
        for(int i = 0; i < nums.length; i++){
            // sum 值大于 x，将当前值作为新的分割子数组的开头
            if(sum + nums[i] > x){
                cnt++;
                sum = nums[i];
            }else{
                sum += nums[i];
            }
        }
        return cnt <= m;
    }
}

时间复杂度O(n * log(sum - maxn))，sum 表示数组 nums 中所有元素的和，maxn表示数组所有元素的最大值，每次二分查找时，需要对数组进行一次遍历。

空间复杂度O(1)。妙啊！！！