Split Array Largest Sum

Given an array which consists of non-negative integers and an integerm, you can split the array intomnon-empty continuous subarrays. Write an algorithm to minimize the largest sum among thesemsubarrays.

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

Approach #1 Brute Force [Time Limit Exceeded]

Intuition

Check all possible splitting plans to find the minimum largest value for subarrays.

Algorithm

We can use depth-first search to generate all possible splitting plan. For each element in the array, we can choose to append it to the previous subarray or start a new subarray starting with that element (if the number of subarrays does not exceedm). The sum of the current subarray can be updated at the same time.

Complexity Analysis

• Time complexity :O(nm)O(n​m​​). To splitnelements intomparts, we can have(n−1m−1)(​m−1​n−1​​)different solutions. This is equivalent tonmn​m​​.

• Space complexity :O(n)O(n). We only need the space to store the array.

class Solution {
    private int ans;
    private int n, m;
    private void dfs(int[] nums, int i, int cntSubarrays, int curSum, int curMax) {
        if (i == n && cntSubarrays == m) {
            ans = Math.min(ans, curMax);
            return;
        }
        if (i == n) {
            return;
        }
        if (i > 0) {
            dfs(nums, i + 1, cntSubarrays, curSum + nums[i], Math.max(curMax, curSum + nums[i]));
        }
        if (cntSubarrays < m) {
            dfs(nums, i + 1, cntSubarrays + 1, nums[i], Math.max(curMax, nums[i]));
        }
    }
    public int splitArray(int[] nums, int M) {
        ans = Integer.MAX_VALUE;
        n = nums.length;
        m = M;
        dfs(nums, 0, 0, 0, 0);
        return ans;
    }
}

Approach #2 Dynamic Programming [Accepted]

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.

Complexity Analysis

• Time complexity :O(n2∗m)O(n​2​​∗m). The total number of states isO(n∗m)O(n∗m). To compute each statef[i][j], we need to go through the whole array to find the optimumk. This requires anotherO(n)O(n)loop. So the total time complexity isO(n2∗m)O(n​2​​∗m).

• Space complexity :O(n∗m)O(n∗m). The space complexity is equivalent to the number of states, which isO(n∗m)O(n∗m).

class Solution {
    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];        
    }
}

Approach #3 Binary Search + Greedy [Accepted]

Intuition

We can easily find a property for the answer:

If we can find a splitting method that ensures the maximum largest subarray sum will not exceed a valuex, then we can also find a splitting method that ensures the maximum largest subarray sum will not exceed any valueythat is greater thanx.

Lets define this property asF(x)for the valuex.F(x)is true means we can find a splitting method that ensures the maximum largest subarray sum will not exceedx.

From the discussion above, we can find out that forxranging from-INFINITYtoINFINITY,F(x)will start with false, then from a specific valuex0,F(x)will turn to true and stay true forever.

Obviously, the specific valuex0is our answer.

Algorithm

We can use Binary search to find the valuex0. Keeping a valuemid = (left + right) / 2. IfF(mid)is false, then we will search the range[mid + 1, right]; IfF(mid)is true, then we will search[left, mid - 1].

For a givenx, we can get the answer ofF(x)using a greedy approach. Using an accumulatorsumto store the sum of the current processing subarray and a countercntto count the number of existing subarrays. We will process the elements in the array one by one. For each elementnum, ifsum + num <= x, it means we can addnumto the current subarray without exceeding the limit. Otherwise, we need to make a cut here, start a new subarray with the current elementnum. This leads to an increment in the number of subarrays.

After we have finished the whole process, we need to compare the valuecntto the size limit of subarraysm. Ifcnt <= m, it means we can find a splitting method that ensures the maximum largest subarray sum will not exceedx. Otherwise,F(x)should be false.

Complexity Analysis

• Time complexity :O(n∗log(sumofarray))O(n∗log(sumofarray)). The binary search costsO(log(sumofarray))O(log(sumofarray)), wheresum of arrayis the sum of elements innums. For each computation ofF(x), the time complexity isO(n)O(n)since we only need to go through the whole array.

• Space complexity :O(n)O(n). Same as the Brute Force approach. We only need the space to store the array.

class Solution {
    public int splitArray(int[] nums, int m) {
        long l = 0;
        long r = 0;        
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            r += nums[i];
            if (l < nums[i]) {
                l = nums[i];
            }
        }
        long ans = r;
        while (l <= r) {
            long mid = (l + r) >> 1;
            long sum = 0;
            int cnt = 1;
            for (int i = 0; i < n; i++) {
                if (sum + nums[i] > mid) {
                    cnt ++;
                    sum = nums[i];
                } else {
                    sum += nums[i];
                }
            }
            if (cnt <= m) {
                ans = Math.min(ans, mid);
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return (int)ans;      
    }
}