Maximum Absurdity this problem was asked in Codeforces Round #193 (Div. 2). Plz anyone tell me what is the approach for solving this problem?

# Two subsequence with maximum sum

This is pretty nice problem So here is my solution.

Problem is find two non-intersecting subsequence each of length exactly *k* with maximal possible sum.

First thing to notice is, that we allways have sequence of length *k*. That means we can compute sum of each subsequence *[a, a+k-1]*. This can be easily done in time *O(n)*. Because if we know sum of sequence *[a, a+k-1]* we easily compute sum for sequence *[a+1, a+k]* (itâ€™s also has length *k*) by adding element in position *a+k* and substract element *a*. So with one travers we know correct values.

Now fix some *b*. We know sum of sequence *[b, b+k-1]* and want to choose *a* such as *a+k-1 < b* and total sum of *[b, b+k-1]* and *[a, a+k-1]* is maximal. And when we have fixed position *b* than we want to find *[a, a+k-1]* with biggest sum. We can do it in time *O(n^2)* - for each *b* find the best *a*.

This is too slow. But we can easily upgrade it. We can compute best *a* for each interval *[0, i]*. You should notice, that these are only interesting segments. We again use simple dynamic programming. If *S_i* is biggest subsequence in interval *[0, i]* than *S_i+1 = max(S_i, sum([i-k+2, i+1]))* is biggest subsequence for interval *[0, i+1]*. And *sum([i-k+2, i+1])* is already known from first transition.

Now we just go trough all possible *b* and pick *S_b-1* as biggest interval for *a*. All is done in time *O(n)*. Here you can check my correct code for this problem.