Longest Increasing Sequence

LongestIncreasingSequence

/*
 * Dynamic Programming Solution
 * f[i] : longest increasing sequence of A[0..i], f[i] = max{f[j]} + 1,  0<= j < i
 * Time complexity : O(n^2) ; Space complexity : O(n)
 */
public int lis(int[] A){
    int n = A.length, maxLength = 0;
    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;
        maxLength = Math.max(maxLength, f[i]);
    }
    return maxLength;
}

/*
 * Greedy + binary Search
 * Time complexity : O(nlgn), Space complexity : O(n)
 *
 */
public int LIS(int[] A){
    int k = 0, n = A.length;
    int[] d = new int[n];
    d[0] = a[0];
    for (int i=1; i<n; i++){
        int j = binarySearch(d, k, A[i]);
        d[j] = A[i];
        if (k < j)
            k++;
    }
    return k+1;
}
/*
 * Return the index of left most element whose value is larger than key. 
 * if no such element found, return the right boundary + 1
 * 
 */
public int binarySearch(int[] array, int low, int high, int key){
    while (low <= high){
        int mid = low + (high - low)/2;
        if (key >= array[mid])
            low = mid+1;
        else
            high = mid-1;
    }    
    return low;
}