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:
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.
Analysis:
A sequence DP problem.
Define dp[n + 1][m + 1], where dp[i][k] means for the first i elements, divide into number of k subarrays, dp[i][k] is the minimum largeset sum among them.
Code (Java):
class Solution { public int splitArray(int[] nums, int m) { int[] preSum = new int[nums.length + 1]; for (int i = 1; i < preSum.length; i++) { preSum[i] = preSum[i - 1] + nums[i - 1]; } int[][] dp = new int[nums.length + 1][m + 1]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[0].length; j++) { dp[i][j] = Integer.MAX_VALUE; } } dp[0][0] = 0; for (int i = 1; i <= nums.length; i++) { for (int j = 0; j < i; j++) { for (int k = 1; k <= m; k++) { dp[i][k] = Math.min(dp[i][k], Math.max(dp[j][k - 1], preSum[i] - preSum[j])); } } } return dp[nums.length][m]; } }
No comments:
Post a Comment