Maximum Subarray III.cpp

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) {
        int len = nums.size();
        if(len < k)return 0;
        //globalMax[i][j] represents max sum we have when doing k partitions with first j elements
        //localMax[i][j] represents max sum we have when doing k partitions with first j elements
        //and the last subarray ends at nums[j]
        //globalMax[i][j] = max(localMax[i][j], globalMax[i][j - 1])
        //localMax[i][j] = max(globalMax[i - 1][k - 1] + sum(nums[k], nums[j - 1])), where i <= k < j
        //from the fomular above, we have
        //localMax[i][j] = max(localMax[i][j - 1], globalMax[i - 1][j - 1]) + nums[j - 1]
        //base case: globalMax[i][0] = 0, globalMax[0][j] = 0, localMax[i][0] = 0, localMax[0][j] = 0
        vector<vector<int>> globalMax(k + 1, vector<int>(len + 1, 0)), localMax(k + 1, vector<int>(len + 1, 0));
        for(int i = 1; i <= k ;++i)
        {
            //can't partite with less than i elemts
            for(int j = i; j <= len; ++j)
            {
                //make sure check the boudary otherwise default 0 may override negative value
                //for example: nums = {-1, 0 , 1}, k = 3
                localMax[i][j] = i == j? globalMax[i - 1][j - 1] + nums[j - 1] : max(localMax[i][j - 1], globalMax[i - 1][j - 1]) + nums[j - 1];
                globalMax[i][j] = j == i? localMax[i][j]: max(localMax[i][j], globalMax[i][j - 1]);
            }
        }
        return globalMax[k][len];
    }
};