[DP]Longest Increasing Subsequence in Java O(n logn) [Rubicon]

1. Problem

Given a integer array with no duplicate integer, find the longest increasing subsequence?

2. Example

 int[] num = [1,6,2,4,5,0]
subsequence = [1],[6],[2],[4],[5],[0], [1,6], [1,5], [1,6,2,5], [1,2,4,5]..etc.
increasing subsequence = [1],[6],[2],[4],[5],[0], [1,6], [1,2], [1,2,4], [1,2,4,5]..etc.

1	6	2	4	5	0
1 LIS = 1	6 1,6 LIS =2	2 1,2 LIS = 2	4 1,2,4 LIS =3	5 1,2,4,5 LIS = 4	0 LIS=1
LIS[0]=LIS[0]=1	LIS[1]=LIS[0]+1=2 since 6 > 1	LIS[2]=LIS[0]+1 = 2 since 2 !> 6 but 2 > 1	LIS[3]=LIS[2]+1=3 since 4 > 2	LIS[4] = LIS[3]+1 =4 since 5 >4	LIS[5] = LIS[5] since 0 !> 5,4,2,6,2

Formula: if ( num[i] > num[j] ) LIS[i] = LIS[j] +1 

3. Implementation in Java

// Time:O(n^2) two for loop, Space:O(n) an array
// For each element in an array, compare it with the elements before it and computer the length of LIS(longest increasing subsequence)

public static int LongestIncreasingSubsequence(int[] num)
{
    int[] L = new int[num.length];
    L[0] = 1;
    //  j  i
    //  1  6
    for (int i = 1 ; i < L.length; i++)
    {
        // for every index, they have their own max
        int max = 0;
        for ( int j = 0; j< i ; j++)
        {
            if( num[i] > num[j] && L[j] > max )
            {
                 max = L[j];
            }  
        }
        L[i] = max +1; // 1. L[1] = 0+1= 1 or 2. no greater than any element or 3. anyway add current element
    }

    int max = 0;
    for (int i = 0 ; i < L.length ; i++)
    {
       if ( L[i] > max )
       {
          max = L[i];
       }
    }
    
    return max;
}

4. Example :

	1	6	2	4	5	0
s={} - initialize s to the empty set	s={1} New largest LIS	s={1,6} - New Largest LIS	s= {1,2} New largest LIS	s={1,2,4} New largest LIS	s={1,2,4,5} New largest LIS	s={0,,2,4,5} New largest LIS
		if num[i] > last element in S, then append X to the end of S	otherwise, find the smaller greater than element in num, change it to num[i] ex. change 6 to 2 Because S is sorted at any time, the element can be found using binary search in log(N).	if num[i] > last element in S, then append X to the end of S	if num[i] > last element in S, then append X to the end of S	otherwise, find the smaller greater than element in num, change it to num[i] ex. change 1 to 0 Because S is sorted at any time, the element can be found using binary search in log(N).

5. Implementation in Java

// Time:O(n logn ) , Space:O(n) an array
// Binary search a sorted array to replace element


        if ( num == null || num.length == 0) {
            return 0;
        }
        if ( num.length == 1){
            return 1;
        }
    
        int[] sortedTable = new int[num.length];
        int len = 0;
        sortedTable[0] = num[0];
        len =1;
        for ( int i = 1 ; i < num.length ; i ++)
        {
            if ( num[i] < sortedTable[0] )
            {
                sortedTable[0] = num[i]; // change it to current value
            }
            else if ( num[i] > sortedTable[len-1] )
            {
                sortedTable[len++] = num[i]; // append 
            }
            else
            {
              // num[i] wants to be current end candidate of an existing subsequence, it will replace ceil value in sortedTable
                sortedTable[ serachInsertPosition(sortedTable,0,len-1,num[i])  ] = num[i];
            }
        }
        return len;
    }
    // 1,2,4,5, Target = 0
    // 0 1 2 3
    private int serachInsertPosition(int[] sortedTable, int l, int r, int target){

        while ( l <= r){
            int m = (l+r)/2;
            if ( sortedTable[m] == target ){
                return m;
            }
            if ( sortedTable[m] > target ){
                r= m-1;
            } else {
                l = m+1;
            }
        }
        return l;
    }

6. References:
http://professorjava.weebly.com/longest-increasing-subsequence.html
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/