410. Split Array Largest Sum (Hard)

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.

Solution 1: DP O(n^2 * m); O(n * m)

Intuition

The problem satisfies the non-aftereffect property. We can try to use dynamic programming to solve it.

The non-aftereffect property means, once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splittingnums[0..i]intojparts, this value will not be affected by how we split the remaining part ofnums.

To know more about non-aftereffect property, this link may be helpful :http://www.programering.com/a/MDOzUzMwATM.html

Algorithm

Let's definef[i][j]to be the minimum largest subarray sum for splittingnums[0..i]intojparts.

Consider thejth subarray. We can split the array from a smaller indexktoito form it. Thusf[i][j]can be derived frommax(f[k][j - 1], nums[k + 1] + ... + nums[i]). For all valid indexk,f[i][j]should choose the minimum value of the above formula.

The final answer should bef[n][m], wherenis the size of the array.

For corner situations, all the invalidf[i][j]should be assigned withINFINITY, andf[0][0]should be initialized with0.

    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        int[] sub = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k < i; k++) {
                    f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
                }
            }
        }
        return f[n][m];        
    }