# K maximum sums of overlapping contiguous sub-arrays  Difficulty Level Hard
Array Dynamic Programming

## Problem Statement  The problem “K maximum sums of overlapping contiguous sub-arrays” states that you are given an array of integers. Find the maximum sum of k-subarrays such that their sum is maximum. These k-subarrays might be overlapping. So, we need to find k-subarrays such that their sum is maximum among other subarrays.

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

Explanation: The subarray having sum = 50 has the maximum value. After that, if we in the left or in the right direction the sum is decreased. So, if we move in the left direction. We can again get a sum of 50 because -10 and 10 cancel each other. But if we move in the right direction, our sum will only keep on decreasing. So, this is the best possible answer we could get.

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

Explanation: Here if we combine any of the two numbers, that will result in a worse solution. So, choosing a single number will be better. Thus, we will choose single numbers -1 -2 -3. Any other combination will give us a worse result.

## Approach for K maximum sums of overlapping contiguous sub-arrays  The problem asks us to find the k maximum sums among all the sums of all the subarray. So, if we think of using Kadane’s algorithm. We won’t be able to solve the problem. Because Kadane’s algorithm can be used to find the maximum sum. But that won’t be able to find the second maximum, third maximum and others. Kadane’s algorithm mainly focuses on finding the first maximum and does not aim to find the next maximum subarray sum. Here we create two arrays of minimumKSum and maximumKSum. We will use a prefix sum array to find the sum of subarrays for the current index. Array minimumKSum keeps the k minimum sum of subarrays. Array maximumKSum keeps the k maximum sum of subarrays. Now for each index, we update the minimumKSum and maximumKSum arrays. After traversing through the array, answer is stored inside maximumKSum.

## Code  ### C++ code to find K maximum sums of overlapping contiguous sub-array

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

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

vector<int> minimumKSum(k, INT_MAX);
minimumKSum = 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 code to find K maximum sums of overlapping contiguous sub-array

```import java.util.*;

class Main{

static void kMaxSubArrays(int input[], int k)
{
int n = input.length;
int prefixSum[] = new int[n];
prefixSum = input;
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;

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`

## Complexity analysis  ### Time Complexity: O(k*N)

Insertion in minimumKSum and insertion in maximumKSum take O(k) time. And we are doing this process inside a loop that is looping over each element of the array. Hence, the overall time complexity is O(k*n).