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.
8+ registered 