# 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 tabulation in# lis_tabdeflis_tab(a):ans,N=0,len(a)ifN!=0:tab=[Noneforiinrange(N)]forninrange(N):tab[n]=0foriinrange(n):ifa[i]<=a[n]:tab[n]=max(tab[n],tab[i])tab[n]+=1ans=max(ans,tab[n])returnans
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.