Top down approach of lis in o(n^2)


#1

Comment body goes here.

int dp[100005];
int n;
int a[100005];
int lise(int idx)
{
if(idx>=n)
return 0;
int &ret=dp[idx];

if(ret!=-1)
    return ret;
ret=1;            //bhai ye us particular character ke liye
for(int i=idx+1;i<n;i++)
{
    if(a[i]>a[idx])
        ret=max(ret,1+lise( i) );
}
return ret;

}

int Solution::lis(const vector &arr)
{

n=arr.size();

for(int i=0;i<n;i++)
a[i]=arr[i];

memset(dp,-1,sizeof(dp));

int ans=0;

for(int i=0;i<n;i++)
    ans=max(ans,lise(i));
return ans;

}