# 重疊的連續子數組的K個最大和

## 例

`arr = {10,-10,20,30,-1,-2}, k = 2`
`50 50`

`arr = {-1,-2,-3,-4}, k = 3`
`-1 -2 -3`

## 推薦碼

### C ++代碼查找重疊的連續子數組的K個最大和

```#include<bits/stdc++.h>
using namespace std;

void kMaxSubArrays(vector<int> input, int k)
{
int n = input.size();
vector<int> prefixSum(n);
prefixSum[0] = input[0];
for(int i=1;i<n;i++)
prefixSum[i] += prefixSum[i-1] + input[i];

vector<int> minimumKSum(k, INT_MAX);
minimumKSum[0] = 0;

vector<int> maximumKSum(k, INT_MIN);
vector<int> currentSum(k);

for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
if(prefixSum[i] < 0 && minimumKSum[j]==INT_MAX)
currentSum[j]=(-prefixSum[i])-minimumKSum[j];
else
currentSum[j] = prefixSum[i] - minimumKSum[j];
}
int j = 0;
for (int l = 0; l < k; l++) {
if (currentSum[j] > maximumKSum[l]) {
maximumKSum.insert(maximumKSum.begin() + l, currentSum[j]);
maximumKSum.erase(maximumKSum.begin() + k);
j++;
}
}
for (int j = 0; j < k; j++) {
if (prefixSum[i] < minimumKSum[j]) {
minimumKSum.insert(minimumKSum.begin() + j, prefixSum[i]);
minimumKSum.erase(minimumKSum.begin() + k);
break;
}
}
}

for (int element : maximumKSum)
cout<<element<<" ";
}

int main()
{
int inputSize;cin>>inputSize;
vector<int> input(inputSize);
for(int i=0;i<inputSize;i++)cin>>input[i];
int k;cin>>k;
kMaxSubArrays(input, k);
}
```
```6
10 -10 20 30 -1 -2
2```
`50 50`

### Java代碼查找重疊的連續子數組的K個最大和

```import java.util.*;

class Main{

static void kMaxSubArrays(int input[], int k)
{
int n = input.length;
int prefixSum[] = new int[n];
prefixSum[0] = input[0];
for(int i=1;i<n;i++)
prefixSum[i] += prefixSum[i-1] + input[i];

int maximumKSum[] = new int[k];
for(int i=0;i<k;i++)
maximumKSum[i] = Integer.MIN_VALUE;

int minimumKSum[] = new int[k];
for(int i=0;i<k;i++)
minimumKSum[i] = Integer.MAX_VALUE;
minimumKSum[0] = 0;

int currentSum[] = new int[k];
for(int i=0;i<k;i++)
currentSum[i] = 0;

for (int i=0;i<n;i++) {
for (int j=0;j<k;j++) {
if(prefixSum[i] < 0 && minimumKSum[j]==Integer.MAX_VALUE)
currentSum[j]=(-prefixSum[i])-minimumKSum[j];
else
currentSum[j] = prefixSum[i] - minimumKSum[j];
}
int j = 0;
for (int l = 0; l < k; l++) {
if (currentSum[j] > maximumKSum[l]) {
maximumKSum[l] = currentSum[j];
for(int z = l+1;z<k;z++)
maximumKSum[z] = maximumKSum[z-1];
j++;
}
}
for (j = 0; j < k; j++) {
if (prefixSum[i] < minimumKSum[j]) {
minimumKSum[j] = prefixSum[i];
for(int z = j+1;z<k;z++)
minimumKSum[z] = minimumKSum[z-1];
break;
}
}
}

for(int i=0;i<k;i++)
System.out.print(maximumKSum[i]+" ");
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int inputSize = sc.nextInt();
int input[] = new int[inputSize];
for(int i=0;i<inputSize;i++)input[i] = sc.nextInt();
int k = sc.nextInt();
kMaxSubArrays(input, k);
}
}
```
```6
10 -10 20 30 -1 -2
2```
`50 50`