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.

answered
**07 Sep '13, 04:27**

5★michal27

1.1k●2●10●17

accept rate:
13%