Project ForgeThe weight of a sequence a0,a1,...,a(n-1) of real numbers is defined as a0+a1/2+...+a(n-1)/2^(n-1). A subsequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0,...,a(n-1), and Y the maximum possible weight of a subsequence of a1,...,a(n-1). Then X is equal to
- Amax(Y, a0+Y)
- max(Y, a0+Y/2)
- Cmax(Y, a0+2Y)
- Da0+Y/2
Explanation
Either the best subsequence of the full array excludes a0 (giving weight exactly Y, computed on a1..a(n-1) with a1 as its own new 'index 0'), or it includes a0. If a0 is included, every subsequently chosen element shifts one position deeper than it would in Y's own indexing, halving each of its weight contributions relative to Y's computation — giving a0 + Y/2. X is the max of these two cases.
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.