CODEWITHSUNDEEP
algorithmlogicdynamic-programmingsubsequence
Nisarg Devani
Nisarg Devani

Reputation: 27

confusing question of maximum possible weight of a subsequence

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?)

Upvotes: 1

Views: 195

Answers (2)

Souvik Pan
Souvik Pan

Reputation: 21

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.

Upvotes: 2

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

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.

Upvotes: 1

Related Questions