Найдите максимальную взвешенную сумму по всем m-подпоследовательностям

Я пытался решить следующую проблему:

Задача взвешенной суммы

Ближайшая проблема, которую я делал раньше, — это алгоритм Кадане, поэтому я попробовал подход «максимальное окончание здесь», что привело к следующей программе на основе DP. Идея состоит в том, чтобы разбить проблему на более мелкие одинаковые проблемы (обычный DP).

#include<stdio.h>
#include<stdlib.h>


main(){
int i, n, m, C[20002], max, y, x, best, l, j;
int a[20002], b[20002];
scanf("%d %d", &n, &m);
for(i=0;i<n;i++){
    scanf("%d",&C[i]);
}
a[0] = C[0];
max = C[0];
for(i=1;i<n;i++){
    max = (C[i]>max) ? C[i] : max;
    a[i] = max;
}

for(l=0;l<n;l++){
    b[l] = 0;
}

for(y=2;y<m+1;y++){

    for(x=y-1;x<n;x++){

        best = max = 0;
        for(j=0;j<y;j++){
        max += (j+1) * C[j];
        }

        for(i=y-1;i<x+1;i++){
            best = a[i-1] + y * C[i];
            max = (best>max) ? best : max;
        }
        b[x] = max;
    }

    for(l=0;l<n;l++){
    a[l] = b[l];                 
    }
}
printf("%d\n",b[n-1]);
system("PAUSE");
return 0;
}

Но эта программа не работает в течение указанного срока (ограничение пространства в порядке). Подскажите, пожалуйста, алгоритм решения этой задачи.

РЕДАКТИРОВАТЬ.

Вот объяснение кода: Как и у Кадане, моя идея состоит в том, чтобы посмотреть на конкретное C[i], затем взять максимальную взвешенную сумму для m-подпоследовательности, заканчивающейся на C[i], и, наконец, взять максимальное значение всех такие значения по всем i. Это даст нам ответ. Теперь обратите внимание, что когда вы смотрите на m-подпоследовательность, оканчивающуюся на C[i], и берете максимальную взвешенную сумму, это эквивалентно взятию максимальной взвешенной суммы (m-1)-подпоследовательности, содержащейся в C[0] в C[i-1]. И это меньшая проблема, которая идентична нашей исходной. Поэтому используем рекурсию. Чтобы избежать двойного вызова функций, составим таблицу значений f[i][j], где f[ii][j] — ответ на задачу, которая идентична нашей задаче с заменой n на i и m на Дж. То есть мы строим таблицу f[i][j], и наш окончательный ответ — f[n-1][m] (то есть мы используем мемоизацию). Теперь, отметив, что для вычисления записи f[i][j] требуется только предыдущий столбец, достаточно оставить только массивы. Это массивы «a» и «b».

Извините за длинное, не могу сдержаться. :(