0 votes 0 votes To be considered as a dynamic programming model...there are 2 properties 1.must have optimal substructure 2.must have overlapping subproblems Only if both are satisfied it is dynamic or any one if satisfied is sufficient A_i_$_h asked Oct 29, 2017 A_i_$_h 393 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments joshi_nitish commented Oct 30, 2017 reply Follow Share here, it is having overlapping subproblems.. Li={1 + Li+1, if A[i] < A[i+1] 1 ,Otherwise } Finally the the length of the longest monotonically increasing sequence is Max(L0,L1,…,Ln−1). suppose, you have to compute L5 at a particular moment, for that you have to recurse like this L5->L4->L3->L2->L1, now, L4, L3, L2 all are overlapping subproblems, which you would have already computed in previous steps and stored them in some array. now, since you have computed and stored the value of L4 in some previous steps, you can directly use it in L5 without following recursive call, it will look like L5->A[L4] // here Array A is storing computed value of L4.. 0 votes 0 votes A_i_$_h commented Oct 31, 2017 reply Follow Share @joshi here there is a case that suppose from starting we encounter an increasing sequence of lenth 3...it then breaks...then after some inputs we agan encounter an increasing sequence which goes upto length 6 now we traverse back to find the max leads to overlapping subproblems and therefore dynamic if the question was we have to find the longest incresing sequence from start then it will not be a dynamic approach right....becz we just keep incerementing a count variable if it is in increasing sequence and when it breaks...just display count have i understood it correct 0 votes 0 votes joshi_nitish commented Oct 31, 2017 reply Follow Share yupes...correct.. 0 votes 0 votes Please log in or register to add a comment.