The weight of a sequence a0, a1, …, an-1 of real numbers is defined as a0 a1/2 … aa-1/2n-1. A subsequence of a sequence 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, a1, …,an-1 and Y the maximum possible weight of a subsequence of a1, a2, …,an-1. Then X is equal to (A) max(Y, a0 Y) (B) max(Y, a0 Y/2) (C) max(Y, a0 2Y) (D) a0 Y/2

Answer: (B)

Explanation: Using concepts of Dynamic Programming, to find the maximum possible weight of a subsequence of X, we will have two alternatives:

1. Do not include a0 in the subsequence: then the maximum possible weight will be equal to maximum possible weight of a subsequence of {a1, a2,….an} which is represented by Y
2. Include a0: then maximum possible weight will be equal to a0 (each number picked in Y will get divided by 2) a0 Y/2. Here you can note that Y will itself pick optimal subsequence to maximize the weight.

Final answer will be Max(Case1, Case2) i.e. Max(Y, a0 Y/2). Hence B).

Why is the 2nd alternative Y/2 using Dynamic programming?

As per my understanding, the alternatives are:

1. without a0, = the maximum possible weight of a subsequence of a1, a2, …,an-1 = Y
2. with a0, = a0 the maximum possible weight of a subsequence of a1, a2, …,an-1 = a0 Y (but in above explaination it takes Y/2. Why?)

CodePudding user response：

Without a0, the subsequence sum is

Y = a1   a2/2   a3/4 ....

With a0 included, the sum becomes

a0   a1/2   a2/4   a3/8 ... = a0   [1/2 * (a1   a2/2   a3/4 ...)] = a0   Y/2

So the correct answer would be option B.

CodePudding user response：

According to the question,
the weight of the subsequence a0, a1, a2,..., an-1 is
X = a0 a1/2 a2/4 .... an-1/2^(n-1)
and, the weight of the subsequence (with a0 not included) a1, a2, a3,..., an-1 is
Y = a1 a2/2 .... an-1/2^(n-2)
Now, to get X from Ywe can observe that
X = a0 a1/2 a2/4 .... an-1/2^(n-1)
=> X = a0 (a1/2 a2/4 .... an-1/2^(n-1))
=> X = a0 1/2(a1 a2/2 .... an-1/2^(n-2))
=> X = a0 1/2(Y)
Now, applying Dynamic Programming, the max weight of the subsequence a0, a1, a2,..., an-1 will be max(Y, X) = max(Y, a0 Y/2) Hence option B is correct.