Maximum Subarray III

Question:

http://www.lintcode.com/en/problem/maximum-subarray-iii/
Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.

Answer

localMax[i][j], means the maximum sum we can get while select j subarrays 

from first i elements, including element i 

globalMax[i][j], means the maximum sum we can get while select j subarrays 

from first i elements, may not including element i 

// state transfer 

localMax[i][j] = max(localMax[i - 1][j] + nums[i - 1], globalMax[i - 1][j - 1] + nums[i - 1]) 

globalMax[i][j] = max(globalMax[i - 1][j], localMax[i][j]) 

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 n = nums.size();
        if (n == 0 || k > n)
            return 0;
        // Use INT_MIN might cause numeric overflow 
        vector<vector<int>> localMax(n+1, vector<int>(k+1, INT_MIN/2));
        vector<vector<int>> globalMax(n+1, vector<int>(k+1, INT_MIN/2));

        localMax[0][0] = globalMax[0][0] = 0;

        for (int i = 1; i <= n; i++) {
             localMax[i][0] = 0;
             globalMax[i][0] = 0;
             for (int j = 1; j <= k; j++) {
                  localMax[i][j] = max(localMax[i-1][j] + nums[i-1], 
                                       globalMax[i-1][j-1] + nums[i-1]);
                  globalMax[i][j] = max(globalMax[i-1][j], localMax[i][j]);
             }
        }
        return globalMax[n][k];
    }
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️