410 Split Array Largest Sum

410. Split Array Largest Sum

1. Question

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

Note: Ifnis the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000

• 1 ≤ m ≤ min(50,n)

Examples:

Input:

nums = [7,2,5,10,8]

m = 2

Output: 18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

2. Implementation

(1) Binary Search

思路：题目的本质是在这数组所有可能的m个subarray的最大sum里找一个最小的，可以利用二分法的思想，找到这个subarrat sum的左边界。做法是找出这个subarray sum的上下限，由于数组的所有元素都是非负的，所以上限就是数组总和，下限就是单独一个元素的最大值(注意，不是最小值，因为是找m个subarray里最大的一个)，在这个范围里做二分

class Solution {
    public int splitArray(int[] nums, int m) {
        int low = Integer.MIN_VALUE, high = 0, mid = 0;

        for (int num : nums) {
            low = Math.max(low, num);
            high += num;
        }

        while (low + 1 < high) {
            mid = low + (high - low) / 2;

            if (!isValid(nums, m - 1, mid)) {
                low = mid + 1;
            }
            else {
                high = mid;
            }
        }
        return isValid(nums, m - 1, low) ? low : high;
    }

    public boolean isValid(int[] nums, int cuts, int target) {
        int sum = 0;
        for (int num : nums) {
            if (num > target) {
                return false;
            }

            if (sum + num <= target) {
                sum += num;
            }
            else {
                --cuts;
                sum = num;
                if (cuts < 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

(2) DP

思路: DP的思想可能比上面的二分法好理解一些. dp[i][j]这里表示用前j个数分成i组的情况下, 能得到的最小的各个子数组和的最大值。

注意的是，为了能够得到子数组的和，我们首先得到sum[]这个累积和数组，同时将dp[i][j]初始化为Integer.MAX_VALUE。那么状态转移怎么推导呢？对于dp[i][j], 我们需要在前j个数字中间找到一个位置k，使得[0, k]分成i - 1组，[k + 1, j]这部分成为独立一组，显然前i - 1组中最小的各数组间的最大值可以用dp[i - 1][k]表示，那么剩下[k + 1, j]这部分的数组和等于 sum[j] - sum[k]. 那么k的范围是多少呢？我们知道对于i - 1组，如果将每个数作为独立一组，那么i - 1组里最少有i - 1个数，又由于k是在前j个数的范围内得到，所以 i - 1 <= k < j。 那么状态转移方程为dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][k], sum[j] - sum[k])), i - 1 <= k < j

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[] sum = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;


        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = i - 1; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][k], sum[j] - sum[k]));
                }
            }
        }
        return dp[m][n];
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(nlog(maxSum - minSum + 1)), n是数组元素个数, 空间复杂度O(1)

DP: 时间复杂度O(m^2 * n), 空间复杂度O(mn)