Untitled

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