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.

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):

?

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

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];     } }