三个无重叠子数组的最大和

/*
 * 思路：
 * 1. 计算每个长度为 k 的子数组的和，使用 Streams 存储在 sums 列表中。
 * 2. 使用 left 和 right 数组记录可以得到最大和的左边和右边的子数组起始位置。
 * 3. 遍历 middle 子数组的起始位置，寻找使得总和最大的三个子数组组合。
 */
 
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        List<Integer> sums = IntStream.range(0, n - k + 1)
                                      .map(i -> IntStream.range(i, i + k).map(j -> nums[j]).sum())
                                      .boxed()
                                      .collect(Collectors.toList());
 
        int[] left = new int[n - k + 1];
        int bestLeft = 0;
        for (int i = 0; i <= n - k; i++) {
            if (sums.get(i) > sums.get(bestLeft)) bestLeft = i;
            left[i] = bestLeft;
        }
 
        int[] right = new int[n - k + 1];
        int bestRight = n - k;
        for (int i = n - k; i >= 0; i--) {
            if (sums.get(i) >= sums.get(bestRight)) bestRight = i;
            right[i] = bestRight;
        }
 
        int[] result = new int[3];
        int maxSum = 0;
        for (int mid = k; mid <= n - 2 * k; mid++) {
            int l = left[mid - k];
            int r = right[mid + k];
            int total = sums.get(l) + sums.get(mid) + sums.get(r);
            if (total > maxSum) {
                maxSum = total;
                result[0] = l;
                result[1] = mid;
                result[2] = r;
            }
        }
        return result;
    }
}