Kth наибольшая сумма непрерывного массива - PullRequest
Новая
       23

Kth наибольшая сумма непрерывного массива

0 голосов
/ 20 апреля 2020

Я попытался написать программу, чтобы найти K-ю наибольшую сумму смежных подмассивов в массиве чисел с отрицательными и положительными числами в C ++. Например:
Ввод: a [] = {20, - 5, -1} k = 3
Вывод: 14.
Объяснение: Вся сумма смежных подмассивов равна (20, 15, 14, -5, -6, -1), поэтому третья по величине сумма равна 14.

Это без использования подхода кучи мин. Я сталкиваюсь с проблемами во время выполнения. Может ли кто-нибудь помочь? 

#include<iostream>
#include<set>
#include<iterator>


using namespace std;
int greatSum(int a[],int n,int num,int k){
    set<int> s;
    set<int>::iterator it;
    if(num==0){
        it=s.begin();
        advance(it,k-1);
        return *it;
    }
    if(num!=0){
        int itr=n-num+1;
        for(int i=0;i<itr;i++){
            int sum=0;
            for(int j=0;j<num;j++)
                sum+=a[j];
            s.insert(sum);
        }

        return greatSum(a,n,num-1,k);

    }

}
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int k;
    cin>>k;
    cout<<greatSum(a,n,n,k);


}
...