Dynamic Programing : Longest Increasing Sequence (LIS)

gistfile1.java

// DP version, Time Complexity : O(n^2)
public int lis(int[] A){
    if (A == null || A.length == 0) return 0;
    int n = A.length;
    int[] f = new int[n];
    for (int i=0; i<n; i++){
        f[i] = 1;
        for (int j=0; j<i; j++){
            if (A[j] <= A[i] && f[j] + 1 > f[i])
                f[i] = f[j] + 1;
        }
    }
    return f[n-1];
}
// O(nlgn) version by using binary search
public int lis(int[] A){
    if (A == null || A.length == 0) return 0;
    int[] d = new int[A.length];
    d[0] = A[0];
    k = 0;
    for (int i=1; i<A.length; i++){
        int j = findFirstGreaterThanElement(d, 0, k, A[i]);
        d[j] = A[i];
        if (d > k)
            k++;
    }
    return k+1;
}

int findFirstGreaterThanElement(int[] A, int low, int high, int key){
    while (low <= high){
        int mid = low + (high - low)/2;
        if (A[mid] <= key)
            low = mid+1;
        else
            high = mid-1;
    }
    return low;
}