1function maxSumOfThreeSubarrays(nums, k) {
2    const n = nums.length;
3    const prefix = new Array(n + 1).fill(0);
4    const left = new Array(n).fill(0);
5    const right = new Array(n).fill(n - k);
6    
7    for (let i = 0; i < n; i++) {
8        prefix[i + 1] = prefix[i] + nums[i];
9    }
10    
11    for (let i = k, total = prefix[k] - prefix[0]; i < n; i++) {
12        if (prefix[i + 1] - prefix[i + 1 - k] > total) {
13            total = prefix[i + 1] - prefix[i + 1 - k];
14            left[i] = i + 1 - k;
15        } else {
16            left[i] = left[i - 1];
17        }
18    }
19    
20    for (let i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
21        if (prefix[i + k] - prefix[i] >= total) {
22            total = prefix[i + k] - prefix[i];
23            right[i] = i;
24        } else {
25            right[i] = right[i + 1];
26        }
27    }
28    
29    let maxSum = 0;
30    const result = [0, 0, 0];
31    for (let i = k; i <= n - 2 * k; ++i) {
32        let l = left[i - 1];
33        let r = right[i + k];
34        let totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
35        if (totalSum > maxSum) {
36            maxSum = totalSum;
37            result[0] = l;
38            result[1] = i;
39            result[2] = r;
40        }
41    }
42    return result;
43}
44
45// Example usage
46const nums = [1, 2, 1, 2, 6, 7, 5, 1];
47const k = 2;
48console.log(maxSumOfThreeSubarrays(nums, k));

1#include <vector>
using namespace std;

vector<int> maxSumOfThreeSubarraysDP(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n, 0);
    vector<int> prefix(n + 1, 0);
    vector<int> left(n), right(n);

    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    for (int i = 0; i < k; ++i) {
        dp[i] = prefix[i + 1];
    }

    for (int i = k; i < n; ++i) {
        if (prefix[i + 1] - prefix[i + 1 - k] >= dp[i - 1]) {
            dp[i] = prefix[i + 1] - prefix[i + 1 - k];
            left[i] = i + 1 - k;
        } else {
            dp[i] = dp[i - 1];
            left[i] = left[i - 1];
        }
    }

    right[n - k] = n - k;
    for (int i = n - k - 1; i >= 0; --i) {
        if (prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]) {
            right[i] = i;
        } else {
            right[i] = right[i + 1];
        }
    }

    vector<int> result(3);
    int maxSum = 0;
    for (int i = k; i <= n - 2 * k; ++i) {
        int l = left[i - 1];
        int r = right[i + k];
        int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
        if (totalSum > maxSum) {
            maxSum = totalSum;
            result = {l, i, r};
        }
    }

    return result;
}

int main() {
    vector<int> nums = {1, 2, 1, 2, 6, 7, 5, 1};
    int k = 2;
    vector<int> result = maxSumOfThreeSubarraysDP(nums, k);
    for (int i : result) {
        cout << i << " ";
    }
    return 0;
}