In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

分析：因为它要求每个subarray size 是一样的，所以我们可以用dp[i]表示从i到i + k - 1的和。
然后，我们再从左往右扫，记录在当前点i，从0到i哪里开始的subarray最大。
同样，我们再从右往左扫，记录在当前点i，从i到n-1哪里开始的subarray最大。
最后，我们看中间那个subarray可以移动的范围，然后不断比较取最大和。

 1 class Solution {
 2     public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
 3         int n = nums.length - k + 1, sum = 0;
 4         int[] dp = new int[n];
 5         for (int i = 0; i < nums.length; i++) {
 6             sum += nums[i];
 7             if (i >= k) {
 8                 sum -= nums[i - k];
 9             }
10 
11             if (i >= k - 1) {
12                 dp[i - k + 1] = sum;
13             }
14         }
15 
16         int[] left = new int[n], right = new int[n];
17         int maxIndex = 0;
18 
19         for (int i = 0; i < n; i++) {
20             if (dp[i] > dp[maxIndex]) {
21                 maxIndex = i;
22             }
23             left[i] = maxIndex;
24         }
25 
26         maxIndex = n - 1;
27         for (int i = n - 1; i >= 0; i--) {
28             if (dp[i] >= dp[maxIndex]) {
29                 maxIndex = i;
30             }
31             right[i] = maxIndex;
32         }
33 
34         int[] res = new int[3];
35         Arrays.fill(res, -1);
36 
37         for (int i = k; i < n - k; i++) {
38             if (res[0] == -1 || dp[res[0]] + dp[res[1]] + dp[res[2]] <
39                 dp[left[i - k]] + dp[i] + dp[right[i + k]]) {
40                 res[0] = left[i - k];
41                 res[1] = i;
42                 res[2] = right[i + k];
43             }
44         }
45         return res;
46     }
47 }