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
public class Solution {
    public int[] MaxSumOfThreeSubarraysDP(int[] nums, int k) {
        int n = nums.Length;
        int[] prefix = new int[n + 1];
        int[] dp = new int[n];
        int[] left = new int[n];
        int[] right = new int[n];

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

        for (int i = k; i < n; ++i) {
            if (prefix[i + 1] - prefix[i + 1 - k] > (dp[i - 1] if i - 1 >= 0 else 0)) {
                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];
            }
        }

        int maxSum = 0;
        int[] result = new int[3];
        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[0] = l;
                result[1] = i;
                result[2] = r;
            }
        }
        return result;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
        int k = 2;
        int[] result = solution.MaxSumOfThreeSubarraysDP(nums, k);
        Console.WriteLine(string.Join(", ", result));
    }
}