lintcode 最大子数组|||

给定一个整数数组和一个整数 k，找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
给出数组 [-1,4,-2,3,-2,3] 以及 k = 2，返回 8。
这道题和前两道题不同，k是未知的，所以不能通过遍历得到结果，因此采用动态规划方法。dp[i][j]表示从前i个数中取j个数组的和的最大值，而dp[i][j]又等于在前i-1个数中取j-1个数组加上第i个数的最大值。

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
        vector<vector<int> > dp(nums.size()+1,vector<int>(k+1,INT_MIN));
        for (int i = 0;i < nums.size();i++) {
            dp[i][0] = 0;
        }
        for (int i = 1;i <= nums.size();i++) {
            for (int j = 1;j <= k;j++) {
                int endmax = 0;
                for (int l = i;l >= j;l--) {
                    endmax = max(nums[l-1],nums[l-1]+endmax);
                    dp[i][j] = max(dp[i][j],dp[l-1][j-1]+endmax);
                }
            }
        }
        return dp[nums.size()][k];
    }
};