Lintcode 43: Maximum Subarray III

https://www.lintcode.com/problem/maximum-subarray-iii/description

Noes:

This question is said to be a classical dp question, but I do not think I had seen this before.

Anyway, the method used here is the so-called "local-global" maximum algorithm.

local[i][j]: represents the maximum value achieved using the first i elements with j non-overlapping groups and ending with the ith element;

global[i][j]: represents the maximum value achieved using the first i elements with j non-overlapping groups  and not necessarily ending with the ith element;

local[j][j] = max (global[i-1][j-1], local[i-1][j]) + nums[i]

The local[i][j] must ends with the ith element, so we need to add it. The ith element can form a group (sub-array) by itself; or it can joins the previous group, which corresponds to the first and the second terms;

global[i][j] = max(global[i-1][j], local[i][j])

For global[i][j], we may or may not use the ith element. If used, it should be local[i][j]; otherwise it is global[i-1][j].

In addition, we need to pay attention to the initialization:

(1) When j > i, it is impossible to form j different non-overlapping groups. In this case, it can be initialized as INT_MIN;

(2) local[i][0] can be initialized as INT_MIN as well, since it is impossible to form this kind of condition;

(3) global[i][0] can be initialized as 0. We simply do no choose any element.

See the code below:

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
        int len = nums.size();
        vector<vector<int>> local(len+1, vector<int>(k+1, INT_MIN)), global(len+1, vector<int>(k+1, INT_MIN));
        //local[i][j]: the maximum sum of j non-overlapping subarrays ending with the ith elements;
        //global[i][j]: the maximum sum of j no-voerlapping subarrays not necessary ending with the ith elements.
        //local[i][j] = max(global[i-1][j-1], local[i-1][j]) + nums[i];
        //global[i][j] = max(global[i-1][j], local[i][j]);
        for(int i=0; i<=len; ++i) global[i][0] = 0;
        for(int i=1; i<=len; ++i) {
            for(int j=1; j<=min(k, i); ++j) {
                local[i][j] = max(global[i-1][j-1], local[i-1][j]) + nums[i-1];
                global[i][j] = max(global[i-1][j], local[i][j]);
            }
        }
        return global[len][k];
    }
};