longest increasing subsequence (LIS)
RU: наибольшая возрастающая подпоследовательность (LIS)
The longest strictly increasing subsequence of an array. A one-dimensional DP solves it in O(n²) with dp[i] as the length of the best subsequence ending at i; binary search over a tails array improves it to O(n log n).