# C++ O(n) time O(n) space concise solution

• Let b[i] be contiguous sum of k elements ending with index i. We need to find the max sum of b[x] + b[y] + b[z] where x + 2k <= y + k <= z. We traverse the array, store solutions for cases of 1 sum (delayed by 2*k steps) , 2 sums (delayed by k steps), 3 sums (no delay) and update those each time we visit new element.

``````class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& a, int k) {
int n = a.size();
vector<int> c[3], m(3); //store optimal solutions for 1 sum, 2 sums, 3 sums.
vector<int> b(n);
int sm = 0;
for (int i = 0; i < n; ++i) {
sm += a[i];
if (i >=k-1) {
b[i] = sm;
sm -= a[i-k+1];
if (i >= 3 * k-1) {
if (b[i-k-k] > m[0]) { // update 1 sum solution
m[0] = b[i-k-k];
c[0] = {i-k-k};
}
if (b[i-k] + m[0] > m[1]) { // update 2 sums solution
m[1] = b[i-k] + m[0];
c[1] = {c[0][0], i-k};
}
if (b[i] + m[1] > m[2]) { //update 3 sums solution
m[2] = m[1] + b[i];
c[2] = {c[1][0], c[1][1], i};
}
}
}
}

return {c[2][0]-k + 1,c[2][1]-k+1,c[2][2]-k+1};
}
};
``````

• @dickchimney Thanks for sharing. Great solution.

• @QQBear You're welcome.

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