• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
const int n = nums.size() - k + 1;
vector<int> sums(n);  // sums[i] := sum of nums[i..i + k)
vector<int> l(n);     // l[i] := index in [0..i] having max sums[i]
vector<int> r(n);     // r[i] := index in [i..n) having max sums[i]

int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (i >= k)
sum -= nums[i - k];
if (i >= k - 1)
sums[i - k + 1] = sum;
}

int maxIndex = 0;
for (int i = 0; i < n; ++i) {
if (sums[i] > sums[maxIndex])
maxIndex = i;
l[i] = maxIndex;
}

maxIndex = n - 1;
for (int i = n - 1; i >= 0; --i) {
if (sums[i] >= sums[maxIndex])
maxIndex = i;
r[i] = maxIndex;
}

vector<int> ans{-1, -1, -1};

for (int i = k; i < n - k; ++i)
if (ans[0] == -1 || sums[ans[0]] + sums[ans[1]] + sums[ans[2]] <
sums[l[i - k]] + sums[i] + sums[r[i + k]]) {
ans[0] = l[i - k];
ans[1] = i;
ans[2] = r[i + k];
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
final int n = nums.length - k + 1;
int[] sums = new int[n]; // sums[i] := sum of nums[i..i + k)
int[] l = new int[n];    // l[i] := index in [0..i] having max sums[i]
int[] r = new int[n];    // r[i] := index in [i..n) having max sums[i]

int sum = 0;
for (int i = 0; i < nums.length; ++i) {
sum += nums[i];
if (i >= k)
sum -= nums[i - k];
if (i >= k - 1)
sums[i - k + 1] = sum;
}

int maxIndex = 0;
for (int i = 0; i < n; ++i) {
if (sums[i] > sums[maxIndex])
maxIndex = i;
l[i] = maxIndex;
}

maxIndex = n - 1;
for (int i = n - 1; i >= 0; --i) {
if (sums[i] >= sums[maxIndex])
maxIndex = i;
r[i] = maxIndex;
}

int[] ans = {-1, -1, -1};

for (int i = k; i + k < n; ++i)
if (ans[0] == -1 ||
sums[ans[0]] + sums[ans[1]] + sums[ans[2]] < sums[l[i - k]] + sums[i] + sums[r[i + k]]) {
ans[0] = l[i - k];
ans[1] = i;
ans[2] = r[i + k];
}

return ans;
}
}
``````

## Python

``````class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
ans = [-1] * 3
subarrayCount = len(nums) - k + 1
dp = [0] * subarrayCount
sum = 0

for i, num in enumerate(nums):
sum += num
if i >= k:
sum -= nums[i - k]
if i >= k - 1:
dp[i - k + 1] = sum

left = [0] * subarrayCount
maxIndex = 0

for i in range(subarrayCount):
if dp[i] > dp[maxIndex]:
maxIndex = i
left[i] = maxIndex

right = [0] * subarrayCount
maxIndex = subarrayCount - 1

for i in reversed(range(subarrayCount)):
if dp[i] >= dp[maxIndex]:
maxIndex = i
right[i] = maxIndex

for i in range(k, subarrayCount - k):
if ans[0] == -1 or dp[left[i - k]] + dp[i] + dp[right[i + k]] > dp[ans[0]] + dp[ans[1]] + dp[ans[2]]:
ans = [left[i - k], i, right[i + k]]

return ans
``````