longest increasing subsequence

아래 문제를 보자.

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

N^2 with dp

L(i)= i부터 시작해서 끝까지의 lis 라고 정의 하면 L(i-1)=L(i)+1 if a(i-1)<a(i)의 식이 성립한다. 따라서 아래처럼 구현.

int lis_dp(int[] a){
       int N = a.length;
       if(N==0) return 0;

       int[] dp = new int[N];
       int ret =1;
       for(int i=N-1;i>=0;i--){
           dp[i]=1;
           for(int j=i+1;j<N;j++){
               if(a[i]<a[j]){
                   dp[i] =Math.max(dp[i], dp[j]+1);
               }
           }
           ret=Math.max(ret, dp[i]);
       }

       return ret;
   }

nlogn with binary search

binary search를 사용하면 nlogN도 가능하다. sorted array를 유지하면서 하나씩 추가하는데, tail보다 큰 수가 들어오면 tail에 추가하고, 그 이하의 값이 들어오면 기존 값을 binary search를 이용해서 insertion point에 업데이트 한다.

int lis(int[] a){
       int N = a.length;
       if(N==0) return 0;

       int[] dp = new int[N];
       int ret=1;
       int last=0;
       dp[0]=a[0];
       for(int i=0;i<N;i++){
           if(dp[last]<a[i]) {
               dp[++last]=a[i];
               ret = last+1;
               continue;
           }
           int pos = bisect(dp, 0, last, a[i]);
           dp[pos]=a[i];
       }
       return ret;
   }

problems

• lis @leetcode
• OceanView @codejam 2013

reference

• my implementation & test cases