# Concise C++ General DP solution with explanation

• ``````// 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;
}
};
``````

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