Two subsequence with maximum sum

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

This is pretty nice problem :slight_smile: 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.

1 Like