Longest Increasing Subsequence in O(N log N)

In the last post we have seen dynamic programming approach which takes O(n^2) time. We can improve the algorithm to take O(N log N) time.The basic idea behind algorithm is to keep list of LIS of a given length ending with smallest possible element. Constructing such sequence

1. Find immediate predecessor in already known last elements sequence ( lets say its of length k)
2. Try to append current element to this sequence and build new better solution for k+1 length

Because in first step you search for smaller value then A[i] the new solution (for k+1) will have last element greater then shorter sequence. Now the improvement happens at the second loop, basically, you can improve the speed by using binary search. Besides the array dp[], let's have another array c[], c is pretty special, c[i] means: the minimum value of the last element of the longest increasing sequence whose length is i.

Java Code:

public class IncreasingSeqInLog {

	public static int binary_search(int A[], int len, int key) {
		int l = 1, r = len;
		int m;
		while (r - l > 1) {
			m = l + (r - l) / 2;
			if (A[m] >= key)
				r = m;
			else
				l = m;
		}
		return r;
	}

	public static int LongestIncreasingSubsequenceLength(int array[], int len) {
		int sz = 1;
		int c[] = new int[len + 1];
		int dp[] = new int[len];
		c[1] = array[0];
	/* at this point, the minimum value of the last element of the size 1
	 * increasing sequence must be array[0] */
		dp[0] = 1;
		for (int i = 1; i < len; i++) {
			if (array[i] < c[1]) {
				c[1] = array[i];
	//you have to update the minimum value right now
				dp[i] = 1;
			} else if (array[i] > c[sz]) {
				c[sz + 1] = array[i];
				dp[i] = sz + 1;
				sz++;
			} else {
				int k = binary_search(c, sz, array[i]);
	// you want to find k so that c[k-1]<array[i]<c[k]
				c[k] = array[i];
				dp[i] = k;
			}
		}

		return sz;
	}

	public static void main(String args[]) {
		int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
		int size = A.length;

		System.out.println("LIS size "
				+ LongestIncreasingSubsequenceLength(A, size));

	}
}