Longest increasing subsequence
Print the length of the longest strictly increasing subsequence (elements need not be next to each other, but must keep their order).
Reported in: Infosys (DSE / SP, 2021–26) (memory-based)
Input
First line: N. Second line: N integers.
Output
The length of the longest increasing subsequence.
Constraints
1 ≤ N ≤ 10^4.
Example 1
Input:
8
10 9 2 5 3 7 101 18
Output:
4Example 2
Input:
4
7 7 7 7
Output:
1Hint: dp[i] = 1 + the best dp[j] for j < i with a[j] < a[i]. (A binary-search version runs in N log N.)