[LeetCode] 410. Split Array Largest Sum

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:
If n is 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.

Thought process:
Binary search. The range of the answer is between max(nums) and sum(nums). Do a binary search on this range. For every mid value, I check if the array can be split into m sub-arrays, where each sub-array's sum <= mid.

1. If I can, that means mid is too large. Keep the left half.
2. If I can't, that means mid is too small. Keep the right half.

Since I'm to split the array into sub-arrays, I can be greedy when I check if the array can be split into m parts. As soon as current sum exceeds mid, I continue onto the next sub-array.

Solution 1 (binary search + greedy):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class Solution { public int splitArray(int[] nums, int m) { long left = 0; long right = 0; for (int num : nums) { left = Math.max(left, num); right += num; } while (left <= right) { long mid = (left + right) / 2; if (canSplit(nums, m, mid)) { right = mid - 1; } else { left = mid + 1; } } return (int) left; } private boolean canSplit(int[] nums, int m, long cap) { int count = 1; long sum = 0; for (int num : nums) { sum += num; if (sum > cap) { count++; if (count > m) { return false; } sum = num; } } return true; } }

Time complexity:
Say there are n numbers. Binary search takes O(log(sum(nums) - max(nums)). CanSplit takes O(n). The overall time complexity is O(nlog(sum(nums) - max(nums))).

There is a dynamic programming solution as well.

1. Sub-problem: minimize the largest sum among a (a < m) sub-arrays of a sub-array of nums.
2. Function: m is the rows and nums is the columns. f[i][j] = min(max(f[i - 1][k] + nums[k] + nums[k + 1] + ... + nums[j])).
3. Initialization: f[1][i] = prefix sum of nums[i].
4. Answer: f[m][nums.length].

Solution 2 (DP):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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

Time complexity: O(mn^2).
If the prefix sums are stored in a separate array, the space complexity can be optimized by using one-dimensional DP.