Longest Increasing Subsquence : Top Down Approach

#1

My top down approach for this is not working…PLease help

#2

@archa_1712,
Why are you trying to do it top down, bhaiya has explained such a simple bottom up logic and implementation in the video. Make sure you understand that by heart first.
And if you still want to implement it top down, please tell me what are the states of your recursion. I don’t think what you are trying to do is even logically consistent.

#3

It dosen’t mean that if i know the bottom up approach I should not know the top down approach…if someone asks me tell him the top down approach of this problem i would’nt be a able to…its about learning…not about things to do which are easier…if i know the bottom up approach and still not able to do the top down , then what i have learned?

#4

@archa_1712,
I am sorry, I think you misunderstood, I told you bottom up is better, but if you want to do top-down, please tell me the states of your recursion, I don’t think what you are doing(in your top-down code) is logically consistent

#5

I am not able to think properly for the top down approach…like i am not able to think the recursive approach of the problem…! Please tell me step by step how the think for the top down approach…!

#6

@archa_1712,
Let’s think like this, how can you uniquely define a increasing subsequence, obviously, you need to know 2 things about it, firstly, where it ends, i.e which ‘I’ is its ending index, also if you want to expand this subsequence further, you would have to have the largest value achieved by the increasing subsequence till ‘I’.
So that you can compare this value with value at any further index ‘j’ to decide whether a[j] can be added to this subsequence or not.

Also, when you are standing on any index ‘I’ you have 2 choices, whether to include it or not in the yet maximum increasing subsequence. As you cannot decide greedily, you ask recursion to find the answer and return the value. So, you recursive function returns the length of LCS.

int solve(int i, int curr_max) {
if (i == n) return 0;
int q1 = INT_MIN, q2 = INT_MIN;
if (a[i] > curr_max) q1 = 1 + solve(i + 1, a[i]);
q2 = solve(i + 1, curr_max);
return max(q1, q2);
}

#7

okay…

#8

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.