Longest inc subsequnce

#1

plz tell me how to print the longest inc subsequnce …provide its code as well…
also tell how to find longest dec subsequnce…along with code…

#2

@S19LPPP0202
I am writing the code for longest Increasing Subsequence, if you can understand this then you can write for decreasing also, no big deal.

See main code for updating dp[] array is same as that we have in LIS.
here, as we know dp[i] denotes the length of longest increasing subs ending at index ‘i’.
So we need to know that which is the previous index for index ‘i’.

int lengthOfLIS(vector& nums) {
int n = nums.size();
vectorans;
vectordp(n);
vector prev(n, -1); //for storing previous index for every index ‘i’.
int max=0, index=-1; //for max LIS and its index

    for(int i=0; i<n; i++) {
        dp[i]=1;
        for(int j=0; j<i; j++) {
            if(nums[i]>nums[j] && dp[j] + 1 > dp[i]){
                dp[i] = 1+dp[j];
                prev[i] = j;  //we are storing the index of previous indexes
            }
        }
        
        if(dp[i] > max) {
            max = dp[i];
            index = i;
        }   
    }
    
    int i = index; //now starting from the index which has max LIS
    while(max--) {
        ans.push_back(nums[i]);
        i = prev[i];  //move to index from which it came(its previous index)
    }
    
    
    for(int i=ans.size()-1; i>=0; i--) {
        cout<<ans[i]<<" ";  //just printing in reverse order.
    }
    
    return ans.size();
}
#3

plz provide a recursive approach for longest inc subsequence as well along with explaination…

#4

@S19LPPP0202 see it is not about providing the code always, you should do coding by yourself by converting your thoughts and logic into code. I will highly suggest you to write that by yourself then only you will learn things.
Although I have provided the complete code with explanation so if there is some doubt in this then you can ask

#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.