C++ solution in worst time complexity O(n^2)


#1

Comment body goes here.int Solution::lis(const vector &A) {

int n = A.size();
if(n==1)return 1;
if(n==0)return 0;
vector<int>dp(n,1);
for(int i=0;i<n;i++)
{
    for(int j=0;j<i;j++)
    {
        if(A[i]>A[j])
        dp[i] = max(dp[i],dp[j]+1);
    }
}

int max = INT_MIN;
for(int i=0;i<n;i++)
{
    if(dp[i]>max)
    max = dp[i];
}
return max;

}