public class Solution { /** * @param nums: A list of integers * @param k: An integer denote to find k non-overlapping subarrays * @return: An integer denote the sum of max k non-overlapping subarrays */
public int[][] getMaximumSubarray(int[] nums){
int n = nums.length;
int[][] ms = new int[n][n];
int[] preSum = new int[n+1];
for(int i = 1; i <= n; i++){
preSum[i] = preSum[i-1] + nums[i-1];
}
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
int minSum = preSum[i];
int max = Integer.MIN_VALUE;
for(int m = i + 1; m <= j + 1; m++){
max = Integer.max(max, preSum[m] - minSum);
minSum = Math.min(minSum, preSum[m]);
}
ms[i][j] = max;
}
}
return ms;
}
public int maxSubArray(int[] nums, int k) {
// write your code here
int n = nums.length;
int[][] ms = getMaximumSubarray(nums);
int[][] res = new int[n+1][k + 1];
// Arrays.fill(res, Integer.MIN_VALUE);
for(int j = 0; j < k; j++){
res[0][j] = 0;
}
for(int i = 1; i < n + 1; i++){
for(int j = 1; j < k + 1 && j <= i; j++){
int temp = Integer.MIN_VALUE;
for(int x = j - 1; x < i; x++){
temp = Math.max(temp, res[x][j-1] + ms[x][i-1]);
}
res[i][j] = temp;
}
}
return res[n][k];
}
}