I cannot guarantee it is correct, as I have no way of testing it, but here is my code, it gives the right answer at least for the 2 sample testcases and some of my own.

#include <iostream>

#include <algorithm>

#include <cstring>

#include <map>

#define INF 10000000

#define MARK -100000

#define mp make_pair

using namespace std;

const int MAX = 10000 + 7;

int N, K, num[MAX], DP[MAX][100+7], started = -1, result = -INF;

int main(void)

{

cin >> N >> K;

for(int i = 0; i < N; i++)

cin >> num[i];

int t = (num[0] > 0)?num[0]:0;

DP[0][0] = num[0];

for(int i = 1; i <= K; i++)

DP[0][i] = t;

int best = 0;

for(int i = 1; i < N; i++)

{

if(num[i] >= 0)

{

for(int j = 0; j <= K; j++)

DP[i][j] = num[i] + DP[i-1][j];

}

else

{

for(int j = 1; j <= K; j++)

DP[i][j] = max(DP[i-1][j] + num[i], DP[i-1][j-1]);

DP[i][0] = num[i] + DP[i-1][0];

}

best = max(best, DP[i][K]);

}

cout << best << endl;

}

PS: Feel free to ask me if you did not understand anything. Hope it helps.