**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.

## No comments:

Post a Comment