Follow Us :

DT Q27

0. 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

  • Option : 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 om Y will get divided by 2) a0 + Y/2. Here you can note that Y will itself pick optimal subsequence to maximum the weight.
    Final answer will be Max (Case1, Case2) i.e. Max (Y, a0 + Y/2). Hence B.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *