Как найти подмассив с минимальной длиной k и максимальной суммой?

Подмассив содержит как положительные, так и отрицательные числа. Вы должны найти подмассив максимальной суммы, такой, чтобы длина подмассива была больше или равна k.

Вот мой код на C ++ с использованием алгоритма Кадане.

#include <iostream>

using namespace std;

int main(){

    int n,k;
    cin >> n >> k;
    int array[n];
    int sum = 0;
    int maxsum = 0;
    int beststarts[n];

    for(int i = 0;i < n; i++){
            cin >> array[i];
    }

    for(int i = 0;i < k-1;i ++){
            sum = sum+array[i];
            beststarts[i] = 0;
    }


    for(int i =  k-1;i < n; i++){ //best end search with min length;
            sum = sum+array[i];
            int testsum = sum;
            if(i > 0){
            beststarts[i] = beststarts[i-1];
            }
            for(int j = beststarts[i] ;i-j > k-1;j ++){
                    testsum = testsum - array[j];
                    if(testsum > sum){
                            beststarts[i] = j+1;
                            sum = testsum;
                    }
            }
            if(sum > maxsum){
                    maxsum = sum;
            }
    }

    cout << maxsum;

    return 0;
}

Мой код работает нормально, но очень медленно, и я не могу придумать никаких способов улучшить свой код. Я также прочитал этот вопрос Найдите самый длинный подмассив, сумма которого делится на K но это не то, что я хочу, длина также может быть больше k.


c++ algorithm dynamic-programming kadanes-algorithm
person 2147483647    schedule 02.11.2012    source источник
comment
Просто как побочный комментарий. Это недопустимый C ++. C ++ не позволяет объявлять массивы с неконстантными значениями. Это что-то из стандарта C99, который некоторые компиляторы C ++ выбрали для поддержки. (См. stackoverflow.com/q/737240/416574)   -  person pstrjds    schedule 02.11.2012
comment
@pstrjds Я знаю об этом, но он поддерживается моим компилятором (Gcc), так почему бы не использовать его!   -  person 2147483647    schedule 02.11.2012
comment
Я не говорил не использовать его :) Я просто хотел указать на это на случай, если кто-то другой увидит это и расстроится со своим компилятором, потому что он не будет компилироваться.   -  person pstrjds    schedule 02.11.2012
comment
возможный дубликат алгоритма суммы подмножества   -  person larsmoa    schedule 02.11.2012

Ответы (1)


arrow_upward
3
arrow_downward

Решение, основанное на этом ответе

Живая демонстрация

#include <algorithm>
#include <iterator>
#include <iostream>
#include <numeric>
#include <ostream>
#include <utility>
#include <vector>

// __________________________________________________

template<typename RandomAccessIterator> typename std::iterator_traits<RandomAccessIterator>::value_type
max_subarr_k(RandomAccessIterator first,RandomAccessIterator last,int k)
{
    using namespace std;
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
    if(distance(first,last) < k)
        return value_type(0);
    RandomAccessIterator tail=first;
    first+=k;
    value_type window=accumulate(tail,first,value_type(0));
    value_type max_sum=window, current_sum=window;
    while(first!=last)
    {
        window += (*first)-(*tail) ;
        current_sum = max( current_sum+(*first), window );
        max_sum = max(max_sum,current_sum);
        ++first;
        ++tail;
    }
    return max_sum;
}

// __________________________________________________

template<typename E,int N>
E *end(E (&arr)[N])
{
    return arr+N;
}

int main()
{
    using namespace std;
    int arr[]={1,2,4,-5,-4,-3,2,1,5,6,-20,1,1,1,1,1};
    cout << max_subarr_k(arr,end(arr),4) << endl;
    cout << max_subarr_k(arr,end(arr),5) << endl;
}

Выход:

14
11
person Community    schedule 02.11.2012