506. Longest Increasing Subsequence Length (Patience Sort + BS)

Given an array, return the length of the longest strictly increasing subsequence. Use the patience-sorting technique: maintain the smallest possible tail for each subsequence length and binary search insertion points. Input: an array of integers.

Input: An array of integers.

Output: Integer — the LIS length.

Examples

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: e.g. [2,3,7,101].

Input: [0,1,0,3,2,3]
Output: 4
Explanation: [0,1,2,3].

Input: [7,7,7,7]
Output: 1
Explanation: All equal.

Constraints

• 0<=n<=2500
• -10^4<=value<=10^4

Asked by