Longest increasing subsequence

#1

the problem in which recursive solution is there its easy to recognize that its a dp problem but in this question how its a dp problem

#2

Yes this is also a dp problem as a recursive (or top down approach) also exists to this.
For every element we can make two choices

  1. If element is greater than previous chosen element ,then we either choose this element as next element in subsequence, or we ignore this element and move forward,
  2. If element is smaller than previous chosen element ,then we have to ignore this element and move forward.
    This can be done as:
    int LIS(int i,int last){
    if(i==n) // base case
    return 0;
    if(a[i]>a[last]) // point 1
    return max(LIS(i+1,last),LIS(i+1,i));
    return LIS(i+1,last); // point 2
    }
#3

return max(LIS(i+1,last),LIS(i+1,i)); what does this line means

#4

It should have been return max(LIS(i+1,last),1+LIS(i+1,i))
this means that either we consider t current element in LIS (this increases length by 1) else we ignore current element, we return max of these.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.