Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence (elements in order, not necessarily adjacent). In 10 9 2 5 3 7 101 18, one is 2 3 7 101 → length 4.

Input:

• line 1: n
• line 2: n integers

Output: the length.

Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹.

Two levels: the O(n²) DP (dp[i] = 1 + max dp[j] over j < i with a[j] < a[i]) passes the small tests. The large tests need O(n log n): keep tails[k] = the smallest possible tail of an increasing subsequence of length k + 1, and place each number with binary search.