# input: a[0..N) array of numbers# output: longest increasing subsequence of a[0..N)## solution by DP in O(N^2) time and O(N) space with memoization in# lis_memoizationdefaux_memoization(a,n,memo):assertlen(a)>0and0<=n<len(a)ans=memo[n]ifans==None:ans=0foriinrange(n):ifa[i]<=a[n]:ans=max(ans,aux_memoization(a,i,memo))ans+=1memo[n]=ansreturnansdeflis_memoization(a):N=len(a)ans=0ifN!=0:memo=[Noneforiinrange(N)]forninrange(N):ans=max(ans,aux_memoization(a,n,memo))returnans
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.