×

# Two subsequence with maximum sum

 0 Maximum Absurdity this problem was asked in Codeforces Round #193 (Div. 2). Plz anyone tell me what is the approach for solving this problem? asked 26 Jul '13, 09:27 227●3●6●9 accept rate: 0% 5★michal27 1.1k●2●10●17

 1 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%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,214
×688

question asked: 26 Jul '13, 09:27

question was seen: 3,586 times

last updated: 07 Sep '13, 12:47