## 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 = 10, LIS = 10     * arr = 22, LIS = 22     * arr = 11, LIS = 22 ... is wrong already, in this case, LIS should      * be LIS = 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= 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 = 1 + LIS = 1+1 = 2                // LIS = 1 + LIS = 1+2 = 3;                // LIS = 1 + LIS = 1 + 0 = 1 because arr= 9                // so there is  no previoius element less than him                // without this condition check                // LIS = 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 );
}
}
```
This entry was posted in programming and tagged . Bookmark the permalink.