Использование объявлений массивов показывает ошибку времени выполнения, но работает нормально при использовании объявления вектора. Зачем? - PullRequest
Новая
       4

Использование объявлений массивов показывает ошибку времени выполнения, но работает нормально при использовании объявления вектора. Зачем?

0 голосов
/ 25 мая 2020

Это решение проблемы максимальной суммы K-разделов, когда я использую объявления массива, он показывает ошибку времени выполнения, но отлично работает с объявлениями векторов. Не могу понять почему? Чем они отличаются?

Максимальная сумма K-разделов Постановка задачи : У Сираджа есть массив из N целых чисел и целого числа K. Он хочет создать подпоследовательность этого массива с применяются некоторые условия. Он строит ceil (N / K) блоков этого массива с размером каждого блока как [i ∗ K + 1, min ((i + 1) ∗ k, N)] для 0≤i≤N / K. Для двух последовательных целых чисел в этой подпоследовательности он хочет, чтобы целые числа были из двух разных блоков. (Не обязательно иметь одно целое число из каждого блока). Кроме того, допустим, что индексы любых двух целых чисел этой подпоследовательности равны i и j, тогда он хочет | i − j | ! = K. Сирадж берет сумму целых чисел в подпоследовательности. Он задается вопросом, какую максимальную сумму можно получить? Помогите сираджу в этой проблеме. 

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll maxsum(ll arr[], ll n, ll k){

    ll dp[n]={0};   // vector<ll> dp(n,0);
    ll max1=INT_MIN;
    ll max2=INT_MIN;
    ll maxind=-1;
    ll i = 0;
    for(i = 0 ; i < k ;i++){
        dp[i] = arr[i];
        if(arr[i] > max1){
            max2 = max1;
            max1 = arr[i];
            maxind = i;
            continue;
        }
        max2 = max(max2 , arr[i]);
    }


    while(count--){
        pos = i;
        for( ; i < min(n, pos+k) ; i++){
            dp[i] = arr[i];
            if(arr[i] >= 0 ){
                if(abs(i-maxind) != k){
                    dp[i] += max1;
                }else
                dp[i] += max2;
            }else
            dp[i] = max1;
        }

        for(i  = pos ; i < min(n,pos+ k) ; i++){
            if(dp[i] > max1){
                max2 = max1;
                max1 = dp[i];
                maxind = i;
                continue;
            }
            max2 = max(max2, dp[i]);
        }
    }    
    return max1;
}
int main(){
    ll n,k;
    cin>>n>>k;
    ll a[n];   //vector<ll> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    cout<<maxsum(a,n,k)<<"\n";
return 0;
}
...