dp[n][k] = max{dp[n-1][k] or a[n], dp[n-1][k-1]}
any hints?? thank you.

Edited by author 18.01.2017 13:16

3 2
7 6 1
Answer: 7

3 2
6 1 7
Answer: 7

because DP like this doesn't work
lets consider next case
3 1
90 75 20

when we calculate last step we have:
dp[3][1] = max(dp[2][1] or 20, dp[2][0])
now dp[2][1] = 90, dp[2][0] = 90 or 75 = 91
we are choosing max between (90 or 20) and 91, which is equal to 94
but this is incorrect answer
correct answer is 75 or 20 = 95