The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+25 votes

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below.

Let $L_i$, denote the length of the longest monotonically increasing sequence starting at index $i$ in the array.

Initialize $L_{n-1} = 1$.

For all $i$ such that $0 \leq i \leq n-2$

$ L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases} $

Finally, the length of the longest monotonically increasing sequence is $\text{max} \:(L_0, L_1, \dots , L_{n-1}).$

Which of the following statements is **TRUE**?

- The algorithm uses dynamic programming paradigm
- The algorithm has a linear complexity and uses branch and bound paradigm
- The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
- The algorithm uses divide and conquer paradigm

+3

here dynamic programming is actually not applied.without using dynamic programming,we can't get linear time complexity here.because,there is no repeating subproblems.

0

how can u say there are no repeating subproblems, while solving longest increasing subsequence, first u calculate the subsequence of length 1, then length 2 and so on.... and while solving subsequences of length n+1, u are using the information where u have solved the longest subsequence of length n, hence repeating subproblems and hence Dynamic Programming.

+1

this given algo is not taking help of dynamic programming.if we need to take the advantage of dynamic programming here,then we have to start calculating values from L_{n-1} up to 0.but here they are computing from 0 to L_{n-1.}

0

@ Sambit Kumar there are no such prerequisites for dynamic programming that it has to be solved by computing from L_{n-1} up to 0. It can be applied in both top-down or bottom-up ways.

Refer:https://www.codechef.com/wiki/tutorial-dynamic-programming

+43 votes

Best answer

$(A)$ is the answer.

The algorithm is storing the optimal solutions to subproblems at each point (for each $i$), and then using it to derive the optimal solution of a bigger problem. And that is dynamic programming approach. And the program has linear time complexity.

http://stackoverflow.com/questions/1065433/what-is-dynamic-programming

Now, branch and bound comes when we explore all possible solutions (branch) and we backtrack as soon as we realise we won't get a solution (in classical backtracking we will retreat only when we won't find the solution). In backtracking : In each step, you check if this step satisfies all the conditions.

If it does : you continue generating subsequent solutions

If not : you go one step backward to check for another path

So, backtracking gives all possible solutions while branch and bound will give only the optimal one. http://www.cs.cornell.edu/~wdtseng/icpc/notes/bt2.pdf

The given algorithm here is neither backtracking nor branch and bound. Because we are not branching anywhere in the solution space.

And the algorithm is not divide and conquer as we are not dividing the problem and then merging the solution as in the case of merge sort (where merge is the conquer step).

0

**@arjun Sir **

how the program has linear time complexity .As per my knowledge the best algo present to find longest increasing subsequence is O(n logn) time.

0

Sir , I have gone through this link and it is mentioned that its O(nlogn) time ,so how is it implemented using dynamic programming.

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

0

@Abhishek The algorithm is given in question. Now you can see if it is finding the "longest monotonically increasing sequence or not".

@Radha You can compare the algos- they are both solving different problems.

@Radha You can compare the algos- they are both solving different problems.

+3

Arjun sir, I think it's finding the longest subsequence which is present contiguously. Ideally subsequence need not have contiguous elements. Am I right?

0

Sir I dont think this is correct answer... As someone has commented above

"this given algo is not taking help of dynamic programming.if we need to take the advantage of dynamic programming here,then we have to start calculating values from L_{n-1} up to 0.but here they are computing from 0 to L_{n-1.}"

This should not be dynamic programming. It looks like Brute Force approach to me.. Please check the question and ur answer again... Correct me if I am wrong

0

@Arjun sir :-

1.The sequence will be of continues ,right?We cannot get subsequence as this algo do not work for that?

2.But here what do the word monotonically means in question?My thinking is that if two elements are same then they should both be considered as part of sequence but the algo checks for strictly increasing sequence.

+1

@anchitjindal07, @Sambit Kumar

if we need to take the advantage of dynamic programming here,then we have to start calculating values from L

_{n-1}up to 0.but here they are computing from 0 to L_{n-1.}

Though that is not the criteria to identify whether a problem can be solved using DP, still if you want to take help of previously computed result then make the L of higher index as the previously computed one. What i mean to say is lets start from index(n-2) and go backwards. In that way we can use the recurrence relation given in the question.

L[n-1]=1 for(i=n-2;i>=0;i--) { if(A[i+1]>A[i]) { L[i]=L[i-1]+1 } else L[i]=1 }

Doubt :

"longest

monotonicallyincreasing sequence"

and the given recurrence relation has condition L_{i}=1+L_{i+1} where A[i]**<**A[i+1]. Why not **≤ **?

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 590
- Exam Queries 575
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,397 questions

53,563 answers

185,728 comments

70,837 users