1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
6    int n = nums.size();
7    vector<int> prefix(n + 1, 0);
8    for (int i = 0; i < n; i++) {
9        prefix[i + 1] = prefix[i] + nums[i];
10    }
11    vector<int> left(n, 0), right(n, n - k);
12    for (int i = k, total = prefix[k] - prefix[0]; i < n; i++) {
13        if (prefix[i + 1] - prefix[i + 1 - k] > total) {
14            left[i] = i + 1 - k;
15            total = prefix[i + 1] - prefix[i + 1 - k];
16        } else {
17            left[i] = left[i - 1];
18        }
19    }
20    for (int i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
21        if (prefix[i + k] - prefix[i] >= total) {
22            right[i] = i;
23            total = prefix[i + k] - prefix[i];
24        } else {
25            right[i] = right[i + 1];
26        }
27    }
28    vector<int> ans(3, 0);
29    int max_sum = 0;
30    for (int i = k; i <= n - 2 * k; ++i) {
31        int l = left[i - 1], r = right[i + k];
32        int current_sum = prefix[l + k] - prefix[l] + prefix[i + k] - prefix[i] + prefix[r + k] - prefix[r];
33        if (current_sum > max_sum) {
34            max_sum = current_sum;
35            ans = {l, i, r};
36        }
37    }
38    return ans;
39}
40
41int main() {
42    vector<int> nums = {1, 2, 1, 2, 6, 7, 5, 1};
43    int k = 2;
44    vector<int> result = maxSumOfThreeSubarrays(nums, k);
45    for (int i : result) {
46        cout << i << " ";
47    }
48    return 0;
49}

1