#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();
}