算法:求第一个k1 k2 k3最大子数组和

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;

我们有一个整数数组。我们需要报告k1 th k2 th k3最大子数组和。数组大小(高达10 ^ 6)。元素都是+ve和-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.

换句话说，我们必须找到S[K]的值，其中to数组S以递减顺序包含所有可能连续子数组的和。

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

线性解是O(n)还是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;
}

1 个解决方案

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

根据*，你应该可以使用Kadane算法在O(n)中找到1个子数组，所以我的猜测是找到最大的子数组，存储它，然后删除它，再搜索第二个最大的子数组等等……

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

我假设之后你使用了一个版本的Kadane算法来跟踪子数组的索引。

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.

如果你这样做3次，你有3个最大子数组你可以对它们求和。

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)

我看到的唯一限制是，您需要删除O(n)中的一个子数组，或者更少地保留该算法在O(n)中。(你可以不删除它，而是跟踪你是否可以访问的wich索引，wich可能更快)

#1