Maximum Subarray III

Maximum Subarray III

Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

Note

The subarray should contain at least one number

Example

Given [-1,4,-2,3,-2,3],k=2, return 8

------------------------ thinking --------------------------------
http://www.cnblogs.com/lishiblog/p/4183917.html
-----------------------  codes ----------------------------------
class Solution {
public:
    /**
     * @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
     */
    int maxSubArray(vector<int> nums, int k) {
        // write your code here
        //dp[j][i] means the max of j elements with i subarrays
        int dp[nums.size() + 1][k+1];
        for (int i = 0; i <= nums.size(); i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= k; i++) {
            for (int j = i; j <= nums.size(); j++) {
                dp[j][i] = INT_MIN;
                int max = INT_MIN;
                int end_max = -1;
// BUG here -> the edge number should be carefully set
                for (int p = j-1; p >= i-1; p--) {
                    end_max = end_max < 0?nums[p]: end_max+nums[p];
                    max = max > end_max?max:end_max;
                    int val = dp[p][i-1] + max;
                    dp[j][i] = dp[j][i] > val?dp[j][i]:val;
                }
            }
        }
        return dp[nums.size()][k];
    }
};