Function lis_len 

pub fn lis_len(nums: &[i64]) -> usize

LIS — eng uzun qat’iy o’suvchi ketma-ketlik uzunligi, O(n log n) da.

G’oya (sabr o’yini / patience sorting): tails[k] — uzunligi k+1 bo’lgan o’suvchi ketma-ketliklar orasida eng kichik oxirgi element. Har bir yangi son uchun tails da binary search qilib, uni almashtiramiz yoki oxiriga qo’shamiz.

[10, 9, 2, 5, 3, 7, 101, 18]
 tails: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
 javob: 4

tails massivi LIS ning o’zi emas — faqat uzunligi to’g’ri. Haqiqiy ketma-ketlik uchun lis dan foydalaning.

• Time: O(n log n), Space: O(n).

Misol

use rust_algorithms::dp::lis_len;

assert_eq!(lis_len(&[10, 9, 2, 5, 3, 7, 101, 18]), 4);
assert_eq!(lis_len(&[7, 7, 7]), 1);
assert_eq!(lis_len(&[]), 0);