Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently asked questions
4.1.
How do we calculate the number of subarrays of an array?
4.2.
Is kadane's algorithm greedy or DP?
4.3.
What is a prefix sum array?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

K maximum sums of overlapping contiguous sub-arrays

Author Prerna Tiwari
0 upvote

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.
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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

After reading this problem, the first thing that comes to our mind is to use Kadane's Algorithm.

While We can find the maximum contiguous subarray sum of an array using Kadane's Algorithm, here, Kadane's Algorithm does not work. Because in Kadane’s algorithm, we set the maximumSum variable to zero whenever we reach a negative number in the array. Hence, we will miss out on the second and subsequent maximums possibilities and in this problem, we have to get k maximum sums. 

For finding the sum of subarrays for the current index, we will use a prefix sum array.

Array minimumSum keeps track of the k smallest sum of subarrays. And The array maximumSum maintains the k maximum sum of subarrays. 

We update the minimumSum and maximumSum arrays for each index. After traversing the array, the answer is stored within maximumSum.

Algorithm

  1. Calculate the input array's prefix sum.
  2. Consider current, maxi, and mini to be arrays of size k.
  3. For each prefix sum[i] value, 
    1. update current[j] =prefix_sum[i] - mini[j]
    2. maxi will be the sum of maxi and current's maximum k elements 
    3. If the prefix sum is less than the sum of all mini values, include it in mini and delete the maximum element from mini.
  4. return maximum

Implementation in C++

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

int main()
{
    int inputSize;
    cin >> inputSize;
    vector<int> input(inputSize);
    for (int i = 0; i < inputSize; i++)
        cin >> input[i];
    int k;
    cin >> k;

    int n = input.size();

    // calculating prefix sum

    vector<int> prefixSum(n);
    prefixSum[0] = input[0];
    for (int i = 1; i < n; i++)
        prefixSum[i] += prefixSum[i - 1] + input[i];

    // initializing maxi mini and current

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

    vector<int> maximumSum(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 && minimumSum[j] == INT_MAX)
                currentSum[j] = (-prefixSum[i]) - minimumSum[j];
            else
                currentSum[j] = prefixSum[i] - minimumSum[j];
        }
        int j = 0;
        for (int l = 0; l < k; l++)
        {
            if (currentSum[j] > maximumSum[l])
            {
                maximumSum.insert(maximumSum.begin() + l, currentSum[j]);
                maximumSum.erase(maximumSum.begin() + k);
                j++;
            }
        }
        for (int j = 0; j < k; j++)
        {
            if (prefixSum[i] < minimumSum[j])
            {
                minimumSum.insert(minimumSum.begin() + j, prefixSum[i]);
                minimumSum.erase(minimumSum.begin() + k);
                break;
            }
        }
    }

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

 

Input

The given array : {4, -2, 3, -7, 1, -6, -5, 6}, k = 2

 

Output

arr[]={6, 5}

 

Complexity Analysis

Time Complexity: O(k*N)

Insertion into minimumSum and maximumSum takes O(k) time. And we're doing this inside a loop that iterates over each element of the array, i.e., we have a nested loop. Hence, the total time complexity of this approach to calculate the k maximum sum of overlapping contiguous subarray is O(k*n).
Space Complexity: O(N)

We are storing the output in an array. Thus space complexity of this solution is linear.

Check out this problem - Subarray With 0 Sum

Frequently asked questions

How do we calculate the number of subarrays of an array?

The number of array subarrays can be calculated as follows:

In an array, we have:-

1 subarray of length n 

2 subarrays of length n – 1

...... 

n subarrays of length 1 

So the total number of subarrays is 1 + 2 + 3 +... n = (n * (n + 1)) / 2.

Is kadane's algorithm greedy or DP?

Kadane's algorithm can be considered greedy as well as DP. As we can see, we keep a running sum of integers and reset it to zero when it becomes negative(Greedy Part). This is because continuing with a negative sum is far worse than beginning with a new range.

What is a prefix sum array?

Given an array arr[] of size n, its prefix sum array is another array prefixSumArray[] of the same size, such that 

prefixSumArray[i] = arr[0] + arr[1] + arr[2]... arr[i].

Conclusion

In this article, we have discussed the problem K maximum sums of overlapping contiguous sub-arrays. We started with introducing array and subarray, problem statement, example, and implementation of the problem in C++, and finally concluded with the time and space complexity of the algorithm.

We hope you have gained a better understanding of the solution to this problem, and now it is your responsibility to solve the problem and try some new and different approaches to this problem. If you would like to learn more, check out our other articles on Data Structures

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding.

Previous article
K-th Largest Sum Contiguous Subarray
Next article
K maximum sums of non-overlapping contiguous sub-arrays
Live masterclass