Алгоритм для нахождения максимальной суммы элементов в массиве, так что не более k элементов смежны

Я столкнулся с этим вопросом. Для массива, содержащего только положительные значения, вы хотите максимизировать сумму выбранных элементов при ограничении, что ни одна группа из более чем выбранных элементов не смежна. Например, если вход 1 2 3 1 7 9 (n = 6 и k = 2). Выходной сигнал будет равен 21, который исходит от выбора элементов _ 2 3 _ 7 9. Мое простое решение DP – это

#include #include #include long maxsum(int n,int k,long *sums){ long *maxsums; maxsums = malloc(sizeof(long)*n); int i; long add = 0; for(i=n-1;i>=nk;i--){ add += sums[i]; maxsums[i] = add; } for(i = nk-1;i>=0;i--){ int j; long sum =0,max = 0,cur; for(j=0;j<=k;j++){ cur = sum; if((i+j+1) max) max = cur; sum += sums[i+j]; } maxsums[i] = max; } return maxsums[0]; } int main(){ int cases=0,casedone=0; int n,k; long *array; long maxsum = 0; fscanf(stdin,"%d %d",&n,&k); array = malloc(sizeof(long)*n); int i =0; while(casedone < n){ fscanf(stdin,"%ld",&array[casedone]); casedone++; } printf("%ld",maxsum(n,k,array)); } 

Но я не уверен, является ли это эффективным решением. Можно ли еще уменьшить сложность? Спасибо за вашу помощь

    Ваш код правильный (по крайней мере, мысль верна), также, до сих пор, я не нашел никаких ошибочных данных теста. Следуйте своей мысли, мы можем перечислить уравнение DP

    P(v)=max{sum(C[v]~C[v+i-1])+P(v+i+1),0<=i<=k}

    В этом уравнении P (v) означает максимум в {C [v] ~ C [n]} (мы будем обозначать {C [1] ~ C [n]} весь список), поэтому нам просто нужно определить P (1).

    До сих пор я не нашел лучшего решения, но ваш код можно оптимизировать, после определения P (v) вы можете сохранить данные i, поэтому, когда вы найдете P (v-1), вы можете просто сравнить сумму ( C [v-1] + C [v] ~ C [v + i-1]) + P [v + i + 1] с P [v + 1] + C [v], когда i! = K, худшее сложность такая же, но лучшая сложность линейна.

    Я думаю, что это сработает:

     findMaxSum(int a[], int in, int last, int k) { // in is current index, last is index of last chosen element if ( in == size of a[] ) return 0; dontChoseCurrent = findMaxSum(a, in+1, last, k); // If current element is negative, this will give better result if (last == in-1 and k > 0) { // last and in are adjacent, to chose this k must be greater than 0 choseCurrentAdjacent = findMaxSum(a, in+1, in, k-1) + a[in]; } if (last != in-1) { // last and in are not adjacent, you can chose this. choseCurrentNotAdjacent = findMaxSum(a, in+1, in, k) + a[in]; } return max of dontChoseCurrent, choseCurrentAdjacent, choseCurrentNotAdjacent }