The Gateway to Computer Science Excellence

+33 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

+54 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.

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.

+1

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.

+4

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

+1

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.

+2

@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 **≤ **?

52,215 questions

59,981 answers

201,180 comments

94,644 users