## Introduction

**An array** is a data structure that can hold a fixed-size sequential collection of the same type of elements. An array is often regarded as a collection of the same type of variables.

The array comes under one of the essential topics for programming interviews, so an individual must have a thorough understanding of this subject.

A **sub-array** is an array with a length less than or equal to the size of the given array, whose elements are all elements of the given array. A subarray is a contiguous section of an array.

Let us understand the problem statement of K maximum sums of overlapping contiguous sub-arrays

Also Read About, __Array Implementation of Queue__ and __Rabin Karp Algorithm__

### Problem Statement

We will have an array of integers of size N in the problem "K maximum sums of overlapping contiguous sub-arrays." We will have to find the maximum sum of k-subarrays such that their sum is maximum. These k-subarrays with the k-maximum sum could overlap. Hence, we must find k-subarrays whose sum is greater than the sum of all other subarrays.

You need to output an array containing the k maximum sum of sub-arrays in non-increasing order.

Before we deep dive into the solution to this problem, we should look at an example to understand the problem of k maximum sum of overlapping contiguous subarrays better.

### Example

**Input:**

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

**Output:**

`arr[] = {50,49}`

Explanation: The subarray {20, 30} with sum = 50 has the maximum value. After that, if we move in either direction, the sum will decrease. So, moving in the left direction, we can get a sum of 40, as 20 and -20 cancel out each other. moving in the right direction, our sum will be {20+30+(-1)} = 49. So, this is the best answer

**Input:**

`arr = {-1,-5,-17,-20}, k = 2`

**Output:**

`arr[] = {-1,-5}`

Explanation: The sum of any of the two numbers will make the sum lesser. So, choosing a single number will be a better solution. Thus, we will choose single numbers -1 and -5.

## Brute Force Approach

The brute approach to this problem is to find the sum of each and every subarray and then pick the k largest sums from them.

### Algorithm

- Initialize a sumsArray and store the sum of every array in it.
- Sort the array in non-increasing order.
- Pick the first K elements from the array.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
// Recursive function to find the sum of all possible subarrays for the given array
vector<int> sumOfSubArrays;
vector<int> subArraysSum(vector<int> arr, int start, int end)
{
int currentSum = 0;
// Stop if we have reached the end of the array
if (end == arr.size())
return sumOfSubArrays;
// Increment the end point and start from 0
else if (start > end)
{
sumOfSubArrays = subArraysSum(arr, 0, end + 1);
}
// Print the subarray and increment the starting point
else
{
for (int i = start; i < end; i++)
{
currentSum += arr[i];
}
currentSum += arr[end];
sumOfSubArrays.push_back(currentSum);
sumOfSubArrays = subArraysSum(arr, start + 1, end);
}
return sumOfSubArrays;
}
int main()
{
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
int k;
cin >> k;
vector<int> sumOfSubArrays = subArraysSum(arr, 0, 0);
sort(sumOfSubArrays.begin(), sumOfSubArrays.end(), greater<int>());
for (int i = 0; i < k; i++)
{
cout << sumOfSubArrays[i] << " ";
}
cout << endl;
return 0;
}
```

**Input**

`The given array : {10,-20,20,30,-1,-2}, k=2`

**Output**

`arr[] ={50, 49}`

#### Complexity Analysis

**Time Complexity: O(N*N)**

Generating all the subarrays requires O(N*N) time complexity and sorting requires O(NlogN) complexity. Hence total complexity is O(N*N) + O(NlogN) ~ O(N*N).**Space Complexity: O(N)**

We are storing the sum of all subArrays in an Array. Thus space complexity of this solution is linear.