GATE 2010 CS (CS1) – Question 44
The weight of a sequence $a_0,\ldots,a_{n-1}$ is $a_0+a_1/2+\cdots+a_{n-1}/2^{n-1}$. Subsequences preserve order and may delete elements. Let X be the maximum subsequence weight of the full sequence and Y that of $a_1,\ldots,a_{n-1}$. Express X.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) max(Y,a₀+Y/2)
Explanation
A maximizing subsequence either omits a₀ or includes it. Omitting it leaves the optimum Y of the tail. Including it adds a₀ and shifts every selected tail element one position to the right, halving its contribution; the best such weight is a₀+Y/2. Taking the larger gives B.