# 3个非重叠子阵列的最大和

nums [] = {1}
k = 2

{0，3，5}

## 3个非重叠子阵列的最大和的说明

nums [] = {1}，k = 2

sum [] = {3，3，3，8，13，12，6}

left [] = {0，0，0，3，4，4，4}
right [] = {4，4，4，4，4，5，6}

• i = 2，总和[i] = 3
从索引2获得的总和= 3 +（sum [left [2 – 2]]）+（sum [right [2 + 2]]）= 19
• i = 3，总和[i] = 8
从索引3获得的总和= 8 +（sum [left [3 – 2]]）+（sum [right [3 + 2]]）= 23
• i = 4，总和[i] = 13
从索引4获得的总和= 13 +（sum [left [4 – 2]]）+（sum [right [4 + 2]]）= 22

## JAVA代码，用于3个非重叠子数组的最大和

```public class MaximumSumOfThreeNonOverlappingIntervals {
private static int[] findInicies(int[] nums, int k) {
int n = nums.length;

// build sum array that stores the sum of all k length continuous subarrays
int sum[] = new int[n - k + 1];
int currSum = 0;
for (int i = 0; i < k; i++) {
currSum += nums[i];
}

sum[0] = currSum;

for (int i = k;i < n; i++) {
currSum -= nums[i - k];
currSum += nums[i];
sum[i - k + 1] = currSum;
}

// Create left array that stores the index of maximum sum of contiguous array of length k upto that index
int left[] = new int[sum.length];
int best = 0;
for (int i = 0; i < sum.length; i++) {
if (sum[i] > sum[best]) {
best = i;
}
left[i] = best;
}

best = sum.length - 1;
// Create right array that stores the index of maximum sum of contiguous array of length k upto that index
// starting from end
int right[] = new int[sum.length];
for (int i = sum.length - 1; i >= 0; i--) {
if (sum[i] >= sum[best]) {
best = i;
}
right[i] = best;
}

// Initialise ans array as -1
int ans[] = new int[] {-1, -1, -1};
// Traverse in sum array from index k to (sum length - k)
for (int i = k; i < sum.length - k; i++) {
// Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
int l = left[i - k];
int r = right[i + k];
if (ans[0] == -1 ||
(sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
// Update the indices if the max sum is greater than the actual max sum
ans[0] = l;
ans[1] = i;
ans[2] = r;
}
}

// return ans array
return ans;
}

public static void main(String[] args) {
// Example
int nums[] = new int[] {1,2,1,2,6,7,5,1};
int k = 2;

int indices[] = findInicies(nums, k);
for (int i = 0; i < 3; i++)
System.out.print(indices[i] + " ");
System.out.println();
}
}```

## 3个非重叠子数组的最大和的C ++代码

```#include <iostream>
#include <vector>
using namespace std;

void findIndices(int *nums, int k, int n, vector<int> &ans) {
// build sum array that stores the sum of all k length continuous subarrays
int sum[n- k + 1];
int currSum = 0;
for (int i = 0; i < k; i++) {
currSum += nums[i];
}

sum[0] = currSum;

for (int i = k;i < n; i++) {
currSum -= nums[i - k];
currSum += nums[i];
sum[i - k + 1] = currSum;
}

// Create left array that stores the index of maximum sum of contiguous array of length k upto that index
int left[n - k + 1];
int best = 0;
for (int i = 0; i < n - k + 1; i++) {
if (sum[i] > sum[best]) {
best = i;
}
left[i] = best;
}

best = n - k;
// Create right array that stores the index of maximum sum of contiguous array of length k upto that index
// starting from end
int right[n - k + 1];
for (int i = n - k; i >= 0; i--) {
if (sum[i] >= sum[best]) {
best = i;
}
right[i] = best;
}

// Initialise ans array as -1
ans.push_back(-1);
ans.push_back(-1);
ans.push_back(-1);
// Traverse in sum array from index k to (sum length - k)
for (int i = k; i < (n - k + 1 - k); i++) {
// Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
int l = left[i - k];
int r = right[i + k];
if (ans[0] == -1 ||
(sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
// Update the indices if the max sum is greater than the actual max sum
ans[0] = l;
ans[1] = i;
ans[2] = r;
}
}
}

int main() {
int nums[] = {1,2,1,2,6,7,5,1};
int k = 2;
int n = sizeof(nums) / sizeof(nums[0]);

vector<int> ans;
findIndices(nums, k, n, ans);
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
cout<<endl;

return 0;
}```
`0 3 5`