CODEWITHSUNDEEP
algorithmarrays
Tomek Tarczynski
Tomek Tarczynski

Reputation: 2785

Maximum subarray with given number of elements

The maximum subarray problem tries to find contiguous subarray of one dimensional array such that the sum of elements of this subarray is largest. It can be easily solved using dynamic programming.

But what with the case in which there is additional constraint that subarray must have at least k elements. It there any O(n) or O(n*logn) algorithm that solves it?

Upvotes: 0

Views: 625

Answers (1)

Ali Akber
Ali Akber

Reputation: 3800

You can use Sliding Window Algorithm.

Lets give an example :

Original array : 4 -2 6 -10 13 8
Window size    : k = 3
maximum = -inf

In each iteration you have to calculate the value of the current window and check if it is the maximum. 

1st window is : |4 -2 6| -10 13 8  
window sum = 8  
maximum = max(-inf , 8) = 8

First window sum has to be calculated by a simple loop with O(k)

What happens in 2nd window? As you can see, if you just subtract the 1st element of previous window and add new value to the sum you can get the sum of 2nd window. That is : 

2nd window is : 4 |-2 6 -10| 13 8  
Window sum = 8 - 4 + (-10) = -6  
maximum = max(8 , -6) = 8

similarly...

3rd window is : 4 -2 |6 -10 13| 8  
Window sum = -6 - (-2) + 13 = 9  
maximum = max(8 , 9) = 9

4th window is : 4 -2 6 |-10 13 8|  
Window sum = 9 - 6 + 8 = 11  
maximum = max(9 , 11) = 11

So the answer will be = 11

Look, this example is for the fixed window size. That is if the question asked about the maximum sum where elements must be k. If the question says at least k elements. That is elements can be larger than k then you have to do some extra work :

  • You have to store the sum of subtracted elements of the previous window
  • If the subtracted element's sum becomes negative then make it 0 otherwise keep it as it is

  • And each time when calculating the maximum = max(current_max , sum) change it to

    maximum = max(current_max , sum + subtracted_element's_sum)

That's all :)

Complexity : O(n)

A C++ Implementation :

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

int main(){
    int i,j,n,k,x,y;
    cin>>n>>k;
    vector<int>v;
    for(i=0; i < n; i++)
    {
        cin>>x;
        v.push_back(x);
    }
    int sum = 0, prev_sum = 0;
    for(i=0;i<k;i++) // Calculating sum of first window
      sum += v[i];
    int maximum = sum;
    for(i = 1; i + k <= n; i++)
    {
        sum = sum - v[i-1] + v[i+k-1]; // Calculating sum of the next windows
        prev_sum += v[i-1]; // Storing previous subtracted elements sum
        if(prev_sum < 0) // Checking if previous sum becomes negative. If so then make it 0, otherwise skip
          prev_sum = 0;
        maximum = max(maximum, sum + prev_sum); // Saving maximum window sum
    }
    cout<<maximum<<"\n";
}

Upvotes: 1

Related Questions