C++ reursive dp solution


#1

int ans;
int longest(const vector &A,int n,vector &dp)
{
if(n<=1)return n;
if(dp[n-1]!=-1)return dp[n-1];
int mx=1;
for(int i=n-1;i>0;i–)
if(A[i-1]<A[n-1])
mx=max(mx,1+longest(A,i,dp));
ans=max(ans,mx);
longest(A,n-1,dp);
return dp[n-1]=mx;
}
int Solution::lis(const vector &A) {
int n=A.size();
ans=1;
vector dp(n,-1);
longest(A,n,dp);
return ans;
}