Length of Longest Increasing Sequence

In term of figuring out length of LIS, here is a very impressive way to solve it. since it does binary search for each of element, the time complexity is O(nlgn).

The idea is to keep a working array sorted and it's working length is controlled by if a bigger number is introduced into the array.

Binary search utility is supported by Java's Arrays.binarySearch function, which suggest an index the new element should be put to. In the algorithm, for same position, number will be overwritten by smaller numbers, so the content is the the increasing sequence we are looking for, but the length of it is correct. Smart!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

package array; import java.util.Arrays; public class LongestIncreasingSubsequence { public static void main(String[] args){ int a[] = new int[]{7,6,2,4,3,8,9,1,15,14,13,5}; System.out.println(lis(a)); } /** * this algorithm is to keep updating a sorted array, in the sorted array, * the length reflects the max length of increasing sequence, but the content * can be overwrite over the time, so that the content is not the sequence that should be printed. * @param a * @return */ static int lis(int a[]){ if (a==null || a.length==0)return 0; int dp[] = new int[a.length]; int len=0; for(int x: a){ //return position it should be at, limit the len to known increasing length int i = Arrays.binarySearch(dp, 0, len, x); i=(i<0?-(i+1):i);//it'd be negative all any new element //this is where the overwriting happens, //it will overwrite the same index with smaller value //all the numbers in the sequence can be overwritten by smaller numbers, //but it since it's overwritten by smaller numbers, it won't change the sorting order of the one without being overwritten //only the growth of len will change the length of increasing length of sub sequence dp[i] = x; if(i==len)len++; } return len; } }