Longest increasing sequence using DP

#1


where is the error in the code ?

#2

hello @mandeepchohan96
ur recurrence relation is not correct.

when u r considering nth element in ur sequeuence then u r looking only for n-1 th index which is not completely correct .
there may be cases where nth element is their in the answer but n-1 th is not.

ur recurrence should be.

solve(i) = max ( j=0 to i-1 solve(j) + (1 if a[j]<a[i]) )

2 Likes