Maximum Subarray III

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

}