Find maximum length of subsequence in Array? | LeetCode Discuss

Find maximum length of subsequence in Array? | LeetCode Discuss

This is longest Increasing subsequence problem. There is DP solution for this with time complexity O(n^2). LIS[i] = Math.max(LIS[j]) where j<i and num[j] < num[i] or Lis[i] = 1 if it doesn't exist such j
There is O(nlog(n)) solution using binary search. The idea is to iterate through the array from left to right and at each iteration to improve or extend current best LIS. What do I mean. Suppose we have array a = {10, 16, 12, 14}
In the beginning our best LIS is empty , we keep it in array best

1. best = []
2. we read a[0] = 10 and put it in best , best = {10}
3. read a[1] = 16 and put it in best ={10,16} because this extends our best LIS
4. read a[2] = 12, it cannot extend our best LIS , because 12 is less than 16, but we can swap 16 with 12 in best in order to improve our LIS, There is a possibility next numbers to be greater than 12 and less than 16 and to extend best LIS.
   b becomes {10,12}
5. We read a[3] = 14 and b becomes {10,12,14}, because 14 is greater than 12 and it iextends current best solution

Read full article from Find maximum length of subsequence in Array? | LeetCode Discuss