【每日算法Day 55】分割数组的最大值

明天面试结束后开始按照labuladong的GitBook文章来继续下一轮的算法刷题思维训练，今天暂时做一道每日一题，是一道可以使用动态规划或贪心+二分的题目，很有意思。

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

题目描述

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

解题思路

动态规划解法：

public int splitArray(int[] nums, int m) {
    int n = nums.length;
    //dp[i][j]表示前i个数分成j个连续子数组【各自和的最大值】的最小值 j<=i
    //则dp[i][j]=Min(Math.max(dp[k][j-1],sum(k+1,i)))，k从0取到i-1
    int[][] dp = new int[n + 1][m + 1];
    for (int[] row : dp) {
        Arrays.fill(row,Integer.MAX_VALUE);
    }
    //sum数组保存nums的前缀和，便于快速计算nums[i]~nums[j]的和
    int[] sum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }

    dp[0][0] = 0;
    for (int i = 1; i <= n; 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], sum[i] - sum[k]));
            }
        }
    }
    return dp[n][m];
}

贪心+二分查找解法： 我先猜一个mid值，然后遍历数组划分，使每个子数组和都最接近mid（贪心地逼近mid），这样我得到的子数组数一定最少; 如果即使这样子数组数量仍旧多于m个，那么明显说明我mid猜小了，因此 lo = mid + 1; 而如果得到的子数组数量小于等于m个，那么我可能会想，mid是不是有可能更小？值得一试。因此 hi = mid;

public int splitArray(int[] nums, int m) {
    int left = 0, right = 0;
    for (int num : nums) {
        left = Math.max(left, num);
        right += num;
    }
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        int count = 1;
        int group = 0;
        //贪心划分数组并计算划分出的子数组数量
        for (int num : nums) {
            group += num;
            if (group > mid) {
                group = num;
                count++;
            }
        }
        //子数组数量多于m个说明mid猜小了
        if (count > m) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}