long increasing subsequence

package algorithm.weixin;

/**
* LIS of {10, 22, 9, 33, 21, 50, 41, 60, 80} is
* {10, 22, 33, 50, 60, 80}
*
* or
* {10, 22, 11, 9, 12, 13, 33, 21, 50, 41, 60, 80} is
* {10, 11, 12, 13,33, 50, 60, 80}
*
*
* @author xwei
*
*/

public class LongestIncreasingSubsequence {

    /**
     * How to use DP to solve this issue? how to find substructure?
     * assume LIS[i] is a LIS sequence, how to find LIS[i+1]?
     * suppose arr[i] has LIS[m], then for arr[i+1] ==>
     * arr[i+1] : arr[i+1] > LIS[m] ? LIS[m+1] = LIS[m] + 1 : LIS[m]
     *
     * the above analysis is wrong!!! take the second array as an example
     * arr[0] = 10, LIS[0] = 10
     * arr[1] = 22, LIS[1] = 22
     * arr[2] = 11, LIS[2] = 22 ... is wrong already, in this case, LIS[2] should
     * be LIS[2] = 11, then you could get correct sequence.
     *
     * correct analysis
     * let LIS[i] = the lenght of subsequence which include arr[i], hence
     * LIS[i] = 1 + LIS[j] ( j < i && arr[j] < arr[i] )
     *          1 ( if there is no such j )
     *
     *
     *
     *
     * @param arr
     * @return
     */
    public static int findLIS( int[] arr )
    {
        int[] LIS = new int[arr.length];
        LIS[0]= 1;
        for( int i = 1; i < arr.length; i++ )
        {
            for( int j = 0; j < i; j++ )
            {
                // notice LIS[i] < LIS[j] + 1 is very important
                // for {10, 22, 9, 33, 21, 50, 41, 60, 80}
                // when i = 3, LIS[3] = 1 + LIS[0] = 1+1 = 2
                // LIS[3] = 1 + LIS[1] = 1+2 = 3;
                // LIS[3] = 1 + LIS[2] = 1 + 0 = 1 because arr[2]= 9
                // so there is  no previoius element less than him
                // without this condition check
                // LIS[3] = 3 would be overwritten.
                if( arr[i] > arr[j] && LIS[i] < LIS[j] + 1 )
                {
                    LIS[i] = 1 + LIS[j];
                }
            }
        }
        int max = 0;
        for( int i = 0; i < LIS.length; i++ )
        {
            if( LIS[i] > max )
            {
                max = LIS[i];
            }
        }
        return max;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        int result = findLIS( arr );
        System.out.println( result );
        int[] arr1 = {10, 22, 11, 9, 12, 13, 33, 21, 50, 41, 60, 80};
        result = findLIS( arr1 );
        System.out.println( result );

    }

}

Advertisements
This entry was posted in programming and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s