Professor Java
Your Ad Here

Longest Increasing Subsequence

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:
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
A subsequence is 0,4,2,1,5. An increasing subsequence is 0,4,10,14,15. The question is to find the length of the longest increasing subsequence, which has size 6 (0, 2, 6, 9, 13, 15). 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 below:

public static int increasingSubsequence(int[]seq){
    int[]L=new int[seq.length];
    for(int i=1;i<L.length;i++){
      int maxn=0;
      for(int j=0;j<i;j++){
    int maxi=0;
    for(int i=0;i<L.length;i++){

The speed is O(n^2).
Provided by site.
Your Ad Here