LONGEST INCREASING SUBSEQUENCE

ALGORITHM

input array of size n

lis[n]:= 1,1,1,1,....,1; for i=2...n do for j=1....i-1 do if array[i]>array[j] AND lis[i]<=lis[j] then lis[i]:=lis[j]+1; end end end return MAX(lis[0],lis[1],...,lis[n]);

COMPLEXITY

Complexity

• Time:
  • Worst Case:
  • Average Case:
  • Best Case:
• Space:
  • Worst Case: