Untitled
unknown
plain_text
a year ago
1.2 kB
1
Indexable
Never
#include<vector> /* int drive(int curr,int prev,int arr[],int n,vector<vector<int>>&dp){ if(curr==n) return 0; if(dp[curr][prev+1]!=-1) return dp[curr][prev+1]; int include=0; if(prev==-1 || arr[curr]>arr[prev]){ include= 1+drive(curr+1,curr,arr,n,dp); } int exclude=drive(curr+1,prev,arr,n,dp); return dp[curr][prev+1] =max(include,exclude); } int longestIncreasingSubsequence(int arr[], int n) { // Write Your Code here] vector<vector<int>> dp(n,vector<int>(n+1,-1)); return drive(0,-1,arr,n,dp); } */ /* prev in each row of dp goes from -1 to n-1 so total size is n+1 but vector cant have negative index so add 1 to prev everywhere while storing in dp */ int longestIncreasingSubsequence(int arr[], int n){ if(n==0) return 0; vector<int> ans; ans.push_back(arr[0]); for(int i=1;i<n;i++){ //O(n) if(arr[i]>ans.back()) ans.push_back(arr[i]); else{ int index=lower_bound(ans.begin(),ans.end(),arr[i])-ans.begin(); //O(logn) ans[index]=arr[i]; } } return ans.size(); }