CODEWITHSUNDEEP
arraysalgorithm
thoughtful me
thoughtful me

Reputation: 115

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

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;
}

Upvotes: 1

Views: 237

Answers (1)

Julien Rous&#233;
Julien Rous&#233;

Reputation: 1113

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)

Upvotes: 1

Related Questions