1#include <stdio.h>
2#include <stdlib.h>
3
4void maxSumOfThreeSubarrays(int* nums, int numsSize, int k, int* returnSize) {
5    int prefix[numsSize + 1];
6    int left[numsSize];
7    int right[numsSize];
8    int result[3];
9
10    // Calculate the prefix sum array
11    prefix[0] = 0;
12    for (int i = 0; i < numsSize; ++i) {
13        prefix[i + 1] = prefix[i] + nums[i];
14    }
15
16    // Calculate max left subarray positions
17    for (int i = k, total = prefix[k] - prefix[0]; i < numsSize; ++i) {
18        if (prefix[i + 1] - prefix[i + 1 - k] > total) {
19            total = prefix[i + 1] - prefix[i + 1 - k];
20            left[i] = i + 1 - k;
21        } else {
22            left[i] = left[i - 1];
23        }
24    }
25
26    // Calculate max right subarray positions
27    right[numsSize - k] = numsSize - k;
28    for (int i = numsSize - k - 1, total = prefix[numsSize] - prefix[numsSize - k]; i >= 0; --i) {
29        if (prefix[i + k] - prefix[i] >= total) {
30            total = prefix[i + k] - prefix[i];
31            right[i] = i;
32        } else {
33            right[i] = right[i + 1];
34        }
35    }
36
37    // Calculate max sum by considering middle subarray
38    int maxSum = 0;
39    for (int i = k; i <= numsSize - 2 * k; ++i) {
40        int l = left[i - 1];
41        int r = right[i + k];
42        int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
43        if (totalSum > maxSum) {
44            maxSum = totalSum;
45            result[0] = l;
46            result[1] = i;
47            result[2] = r;
48        }
49    }
50
51    *returnSize = 3;
52    for (int i = 0; i < 3; ++i) {
53        printf("%d ", result[i]);
54    }
55}
56
57int main() {
58    int nums[] = {1, 2, 1, 2, 6, 7, 5, 1};
59    int k = 2;
60    int returnSize;
61    maxSumOfThreeSubarrays(nums, 8, k, &returnSize);
62    return 0;
63}

1