1import java.util.Arrays;
2
3public class Main {
4    public static int[] maxSumOfThreeSubarrays(int[] nums, int k) {
5        int n = nums.length;
6        int[] prefix = new int[n + 1];
7        for (int i = 0; i < n; i++) {
8            prefix[i + 1] = prefix[i] + nums[i];
9        }
10        int[] left = new int[n];
11        int[] right = new int[n];
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        int[] result = new int[3];
29        int maxSum = 0;
30        for (int i = k; i <= n - 2 * k; ++i) {
31            int l = left[i - 1];
32            int r = right[i + k];
33            int totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
34            if (totalSum > maxSum) {
35                maxSum = totalSum;
36                result[0] = l;
37                result[1] = i;
38                result[2] = r;
39            }
40        }
41        return result;
42    }
43
44    public static void main(String[] args) {
45        int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
46        int k = 2;
47        System.out.println(Arrays.toString(maxSumOfThreeSubarrays(nums, k)));
48    }
49}

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));
    }
}