Maximum Subarray III

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

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
        if (nums.empty()) {
            return 0;
        }
        // when we have only one subarray
        if (nums.size() == k) {
            int sum = 0;
            for (int i = 0; i < nums.size(); ++i) {
                sum += nums[i];
            }
            return sum;
        }
        // normal condition
        int len = nums.size();
        vector<vector<int>> local(k + 1, vector<int>(len + 1, 0));
        vector<vector<int>> global(k + 1, vector<int>(len + 1, 0));
        for (int i = 1; i < k + 1; ++i) {
            // At most, we have i subarray, if current size < i, no result
            local[i][i-1] = INT_MIN;
            // J >= i, to make sure we have i valid subarray
            for (int j = i; j < len + 1; ++j) {
                local[i][j] = max(local[i][j-1], global[i-1][j-1]) + nums[j-1];
                if (j == i) {
                    global[i][j] = local[i][j];
                } else {
                    global[i][j] = max(global[i][j-1], local[i][j]);
                }
            }
        }
        return global[k][len];
    }
};

Similar problems

x

Tags

x