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

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

#include<stdio.h>
#include<limits.h>
#include<malloc.h>


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>=n-k;i--){
        add += sums[i];
        maxsums[i] = add;
    }

    for(i = n-k-1;i>=0;i--){
        int j;
        long sum =0,max = 0,cur;
        for(j=0;j<=k;j++){
            cur = sum;
            if((i+j+1)<n)
                cur += maxsums[i+j+1];  
            if(cur > 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));
}

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