Longest Increasing Subsequence

#1

I’m not able to figure how to find the longest increasing subsequence using top down approach. Pls help me out.

#2

@priyanshi.agarwal3405 hey,take dp array of same size as array and initialise with 1 as min subsequence will be of length one that is that element itself ,now apko every index of array pr jana hai and then us index ke piche ke sare elements ,current se compare krne hai and agr hmara current bda hai to woh pichla index hmare current subsequence me contribute kr skta hai now ab current dp index or jisse compare krrhe hai us dp index+1(1 is added for current element) agr bda hai to current dp ko update krdo aise hi sab index ke lie krdo and finally traverse dp array and find maximum.Hope you get it :slight_smile:

#3

What you are telling me is the bottom up approach. I want to know about the top down approach. https://ide.codingblocks.com/s/205441 This is the link to my code. Bottom up approach is working fine. Pls help me with the top down implementation. I’m unable to figure out where am I going wrong

#4

@priyanshi.agarwal3405 hey for top down approach use include exclude ,here is pseudo code:
public int LIS(int[] arr) {
return LISLength(arr, INT_MIN, 0);
}

public int LISLength(int[] arr, int prev, int current) {
    if (current == arr.length) {
        return 0;
    }
    int include = 0;
    if (arr[current] > prev) {
        include = 1 + LISLength(arr, arr[current], current + 1);
    }
    int exclude = LISLength(arr, prev, current + 1);
    max(include, exclude);
}

Use memoisation in it.

#5

Sir can you please tell me the mistake in my top down implementation. Sharing the link of my code once again : https://ide.codingblocks.com/s/205441

#6

@ hey,
if(dp[len-1]==-1)
{
dp[len-1]=1;
}
ye wali condition kaise likhi hai ,hm base case me dp ko fill krte hai and recursion call krte time check krte hai us index ki dp fill to nhi hai mtlb agr dp -1 se initialise ki thi to woh -1 hai to recursion pr call krte hai,apne ulta krdia upr three lines me.

#7

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.