Given an unsorted array of integers arr[] , write a program to find the length of the longest increasing subsequence such that all elements of the subsequence are sorted in increasing order.

Problem Note

  • The longest subsequence is not necessarily contiguous, or unique.
  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n^2) complexity. Could you improve it to O(nlogn) time complexity?

Example 1 

Input: arr[] = [3,10,2,1,20] 
Output: 3 
Explanation: The longest increasing subsequence is [3,10,20]


Example 2 

Input: arr[] = [0,8,4,2,10,6,1,9,13,3,11,7,15] 
Output: 6 
Explanation: The longest increasing subsequence in this example is not unique.For instance, [0,4,6,9,11,15] or [0,2,6,9,13,15] or [0,4,6,9,13,15] are other increasing subsequences of equal length in the same input sequence.