You are not logged in. Please login at www.codechef.com to post your questions!

×

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?

asked 26 Jul '13, 09:27

vikrant1433's gravatar image

3★vikrant1433
227369
accept rate: 0%

edited 07 Sep '13, 12:47

michal27's gravatar image

5★michal27
1.1k21017


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.

link

answered 07 Sep '13, 04:27

michal27's gravatar image

5★michal27
1.1k21017
accept rate: 13%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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