Given an unsorted array of integers, write a program to find the length of the longest increasing subsequence such that all elements of the subsequence are sorted in increasing order.
- A 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?
Input: A = [3,10,2,1,20] Output: 3 Explanation: The longest increasing subsequence is [3,10,20]
Input: A = [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.