###### Question 4075 – UGC NET CS 2005 Dec-Paper-2

November 10, 2023###### Question 7812 – Algorithms

November 10, 2023# Question 7788 – Algorithms

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

Correct Answer: C

Question 2 Explanation:

First understand the subsequence is an array is

Ex:

{A, B, C, D}

{A, AB, AC, AD, ABC, ABD, ACD, B, BC, BD, BCD, C, CD, D }

Step-1: Array of elements A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0 ]

Step-2: As per the given question, if they want to find maximum subsequence means

{6,3,13,4,4,12}

= 42

Step-3: But according to given recurrence relation, the sequence should be continuous.

{6,3,13,4,4,12}.

This is not continuous subsequence.

Step-4: The continuous sequence is {6, 3, -1, -2, 13, 4, -9, -1, 4, 12}

Total is {29}.

Ex:

{A, B, C, D}

{A, AB, AC, AD, ABC, ABD, ACD, B, BC, BD, BCD, C, CD, D }

Step-1: Array of elements A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0 ]

Step-2: As per the given question, if they want to find maximum subsequence means

{6,3,13,4,4,12}

= 42

Step-3: But according to given recurrence relation, the sequence should be continuous.

{6,3,13,4,4,12}.

This is not continuous subsequence.

Step-4: The continuous sequence is {6, 3, -1, -2, 13, 4, -9, -1, 4, 12}

Total is {29}.

**Note**: We can’t get more than 29 maximum subsequence sum.19

39

29

09

Subscribe

Login

0 Comments