Check LintCode 43. Maximum Subarray III

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，也想到定义state为f[i][j]表示前i个元素在j个subarray条件下的最大值, i 对应维度 nums，大小nums.size(), j对应维度subarray个数，大小k
        //然后，怎么确定transition function是核心。
        // 站在nums中的某个元素往前看。[-1, 4, -2, 3],比如-2。有几种可能如下：
        //1，-2不放在subarray里。f[i][j] = f[i - 1][j]
        //2, -2放在subarray里。又分两种情况1）-2单独组成一个subarray。f[i][j] = f[i -1][j-1] + (-2); 2)-2在前面的subarray里。这个时候发现状态f[i][j]无法实现第二种情况下的状态转移，因为需要一个状态来表示-2前面的一个元素必须在subarray里，即状态P[i][j], 前i个元素（第i个元素被使用）在j个subarray条件下的最大值。这样f[i][j] = P[i -1][j] + (-2)
        //有了第二个状态，也要实现这个状态的转移方程。
        //还是采用f[i][j]转移相同的分析方法。站在某个元素向前看。有几种可能:
        //1, -2前面的元素被使用。P[i][j] = P[i - 1][j] + (-2)
        //2, -2前面的元素没有使用。P[i][j] = f[i - 1][j - 1] + (-2)?????这个情况分析是错误的！！！！
        //有几种可能(只分析-2被使用的情况！不要考虑其他的元素，只看-2！)：
        //1, -2和前面的元素组一个subarray。P[i][j] = P[i - 1][j] + (-2).
        //2, -2自己组成一个subarray。P[i][j] = f[i - 1][j - 1] + (-2)
        //转移方程分析完成！
        //初始化: f[i][0] = INT_MIN, f[0][j] = INT_MIN. P[i][0] = INT_MIN, P[0][j] = INT_MIN.
        //结果: f[n][k].
        //Finish!
        //代码实现时发现
        //1，初始化错了。f[i][0],f[0][j]以及P应该初始化为0.
        //2，一个重要的条件: 在i等于j时需要 f[i][j] = P[i][j];
             
 
        int n = nums.size();
        if(n < k){
            return 0;
        }
        vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MIN));
        vector<vector<int>> P(n + 1, vector<int>(k + 1, INT_MIN));
        for(int i = 0; i < n + 1; i++){
            f[i][0] = 0;
            P[i][0] = 0;
        }
        for(int i = 0; i < k + 1; i++){
            f[0][i] = 0;
            P[0][i] = 0;
        }
 
        f[0][0] = 0;
        P[0][0] = 0;
        for(int j = 1; j < k + 1; j++){
            //P[j-1][j] = INT_MIN;
             for(int i = j; i < n + 1; i++){
                P[i][j] = max(P[i - 1][j], f[i - 1][j - 1]) + nums[i - 1];
                if(i == j){
                   f[i][j] = P[i][j];
                }
                else{
                 //   f[i][j] = max(P[i][j], f[i - 1][j]);
                int temp = f[i - 1][j];
                f[i][j] = max(f[i -1][j-1], P[i -1][j]) + nums[i - 1];
                f[i][j] = max(f[i][j], temp);
                }

             
            }
        }
        return f[n][k];
    }
};