Concise C++ General DP solution with explanation


  • 0
    // General solution for m non-overlap subarrays, Time and Space complexity is O(mn)
    // m = 3, thus Time and Space complexity is O(n)
    
    // Example Input: [1,2,1,2,6,7,5,1], 2
    
    class Solution {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
            int len = nums.size(), overlap = 3;
    
            // sums for each subarrays    
            // Array content for example input:
            // 3 3 3 8 13 12 6 
            vector<int> sums(len - k + 1); 
            for (int i = 0, j = 0, sum = 0; i < nums.size(); i++) {
                sum += nums[i];
                if (i < k - 1) continue;
                sums[j] = sum; 
                sum -= nums[j++];            
            }
    
            // DP table for max sum of m non-overlap subarrays
            // Table content for example input:
            // 0  0  0  0  0  0  0 
            // 3  3  3  8  13 13 13 
            // 0  0  6  11 16 20 20 
            // 0  0  0  0  19 23 23 
            vector<vector<int>> max_sum(overlap + 1, vector<int>(len - k + 1));
            for (int i = 1, begin = 0; i < overlap + 1; i++, begin += 2) {
                int curr_max = 0, last = 0;
                for (int j = begin; j < len - k + 1; j++) {
                    if (j >= k) last = max_sum[i - 1][j - k];
                    max_sum[i][j] = curr_max = max(curr_max, last + sums[j]);
                }
            }
    
            // Retrieve starting indexes of subarrays with maximum sum from right-bottom of the DP table
            // Index:
            // (0)  1   2  (3)   4   (5)   6
            // Table:
            //  0   0   0   0    0    0    0  
            // (3)  3   3   8    13   13   13 
            //  0   0   6  (11)  16   20   20 
            //  0   0   0   0    19  (23)  23
            vector<int> res(overlap);
            int idx = len - k;
            for (int i = overlap; i > 0; i--) {
                while (idx > 0 && max_sum[i][idx] == max_sum[i][idx - 1])
                    idx--;
                res[i - 1] = idx;
                idx -= k;
            }
         
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.