Longest Increasing subsequence

Given an array of random numbers. Find longest monotonically increasing subsequence (LIS) in the array.

The longest increasing subsequence problem is a dynamic programming problem that calculates the length of a non-contiguous subsequence from a given sequence. For example, given the sequence:
10, 22, 9, 33, 21, 50, 41, 60
An increasing subsequence is 10,22,33,41. Another increasing subsequence is 9,21,41. The question is to find the length of the longest increasing subsequence, which has size 5 (10,22,33, 50,60). Note that the sequence might not be unique, but you need to find the length of the longest subsequence.
The key is to notice this: let L(j) be the length of the maximum subsequence that ends at value j. By definition, L(j)=L(i)+1 for some i<j, and A[i]<A[j], where A is the array. So, L(j)=max(L(i) for all i<j)+1. Loop from j=0 to j=A.length, and return the largest L(j) for the largest increasing subsequence.

Java Code:

public class DynamicLIS {

	/*
	 * lis() returns the length of the longest increasing subsequence in arr[]
	 * of size n
	 */
	public static int lis(int arr[], int n) {
		int i, j, max = 0;
		int lis[] = new int[n];

		/* Initialize LIS values for all indexes */
		for (i = 0; i < n; i++)
			lis[i] = 1;

		/* Compute optimized LIS values in bottom up manner */
		for (i = 1; i < n; i++)
			for (j = 0; j < i; j++)
				if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
					lis[i] = lis[j] + 1;

		/* Pick maximum of all LIS values */
		for (i = 0; i < n; i++)
			if (max < lis[i])
				max = lis[i];

		return max;
	}

	/* Driver program to test above function */
	public static void main(String args[]) {
		int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
		int n = arr.length;
		System.out.println("Length of LIS is " + DynamicLIS.lis(arr, n));
	}
}

The time complexity of this algorithm is O(n^2). We will O(nlogn) solution in our next post.