algorithm:Finding the first k1,k2,k3 th maximum subarray sum

Question

Evening everyone,Straight to the question.

We are given an array of integers.we have to report k1 th,k2 th and k3 th maximum subarray sum.Array size (upto 10^6).Elements are both +ve and -ve. k1,k2,k3<=2200;

In other words, we have to find the value of S[K], where the to array S contains the sums of all possible contiguous sub-arrays in decreasing order.

Is linear solution possible O(n) or O(nlogn)?

My approach was like this(not correct)

I somewhere in my heart knows that this can be solved by sorting the array and using two pointer technique I can find all possible subarray sum.And after sorting intermediate sums,we can address but I could not implement it properly.

Anybody have some other approach or same approach but correct ?

Incase you want to see my implementation to the problem

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nline cout<<"\n"
#define fast ios_base::sync_with_stdio(false)cin.tie(0)
#define ain(A, B, C) assert(IN(A, B, C))
#define ull unsigned long long int
#define ll long long int
#define pii pair<int,int>
#define MAXX 100009
#define fr(a,b,i) for(int i=a;i<b;i++)
vector<int>G[MAXX];
bool vis[MAXX];
int n,k1,k2,k3;
bool cmp(const int &l,const int &r){
    return l>r;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k1>>k2>>k3;
        --k1,--k2,--k3;
        int a[n+1];
        for(int i=0;i<n;i++)cin>>a[i];
        sort(a,a+n);
        int l=0,e=n-1;
        vector<ll>v;
        int sum=0;
        while(e>=l)
        {
            if(a[e]>a[l])
            {
                sum+=a[e];
                v.pb(sum);
                e--;
            }
            else
            {
                sum+=a[l];
                v.pb(sum);
                l++;
            }
        }
        sort(v.begin(),v.end(),cmp);
        cout<<v[k1]<<" "<<v[k2]<<" "<<v[k3]<<endl;
    }
    return 0;
}

How are you going to find a contiguous subarray if you sort the array first and thus lose the adjacence information? And please remove the ream of unused macro definitions. — M Oehm
– M Oehm, Commented Oct 11, 2015 at 10:14
What do you mean by Elements are both +ve and -ve. ? I understand this as the elements are in the range [-ve, +ve]. Where ve is some integral value. Is it correct ? — fjardon
– fjardon, Commented Oct 12, 2015 at 9:08
Sorry for being stupid!!! they are shorthand I use for positive and negative(-10^9 to 10^9 more precisely). — thoughtful me
– thoughtful me, Commented Oct 12, 2015 at 17:58

Julien Rousé · Accepted Answer · 2015-10-11 13:31:23Z

1

According to wikipedia, you should be able to find 1 subarray in O(n) using the Kadane algorithm, so my guess would be to find the maximum subarray, store it, and then remove it and search again for the second maximum subarray etc...

I assume after that you use a version of Kadane algorithm that keep track of the index of the subarray.

pseudo code

init_array(array) //here you initialize your array with the number you want in it
start1,end1,sum1 = kadane(array) // you find the starting index, the ending index and the maximal sum of the subarray
remove(array, start1,end1) // here you remove the subarray in array.

if you do that 3 times, you have your 3 maximum subarray and you can sum them.

The only limitation i see, you need to remove a subarray in O(n) or less to keep the algorithm in O(n). (instead of removing it, you can juste keep track of wich index you can access or not, wich may be faster)

answered Oct 11, 2015 at 13:31

Julien Rousé

1,1111 gold badge16 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

fjardon Over a year ago

The other limitation is that if the initial array is sorted you will remove it entirely at the first iteration...

Julien Rousé Over a year ago

That's true, need to check if the resulting array is not empty, good catch!

fjardon Over a year ago

No I mean the whole algorithm is broken. You must not remove anything from the original array, at least not the way you advise. In a sorted array the Kth max sub array is the array starting at 0 and ending at n-K-1

Pham Trung Over a year ago

This is wrong, what if the second maximum array if a subset of the maximum array? for example, this case [1,2,3] , base on your algo, the maximum array is the entire array, so the second maximum array is [] which is clearly wrong.

Collectives™ on Stack Overflow

algorithm:Finding the first k1,k2,k3 th maximum subarray sum

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related