How recursive solution works in longest increasing subsequence
Dynammic programm5
For any ‘i’ in the range indexes assume that you have already considered a increasing sequence till that index. So, this sequence will have its own maximum till now, i.e the last largest value in the sequence (lets say curr_max). Thus for the current element you have 3 cases possible:
1.) Current element is not eligible to be a part of this sequence, i.e (current_element<=curr_max), so you don’t add it into the sequence. E.g:- {[3,4],2,6,7}, you are currently on 2 and have already considered the subsequence [3,4] till now, thus curr_max=4. So, you don’t include 2 in your sequence i.e {[3,4],2,[6,7]}.
2.) Current element is eligible to be a part of this sequence, i.e (current_element>curr_max), so you greedlily add it into the sequence. E.g:- {[3,4],5,6,7} , you are currently on 5 and have already considered the subsequence [3,4] till now, thus curr_max=4. So you will include 5 and increment the length of sequence i.e {[3,4,5],6,7}.
3.)Current element is eligible to be a part of this sequence, i.e (current_element>curr_max), but you don’t add it into the sequence. E.g:-{[3,4],20,6,7}, you are currently on 20 and have already considered the subsequence [3,4] till now, thus curr_max=4. But you don’t include it in your sequence because there is a possibility of longer sequence i.e {[3,4],20,[6,7]}.