[#5 dp] L D S2
Cho một mảng gồm các số nguyên, hãy tìm chuỗi con giảm dài nhất của của mảng (Một chuỗi được gọi là giảm nếu với bất kì phần tử nào trong chuỗi đấy, phần tử đó đều nhỏ hơn tất cả các phần tử đứng trước nó)
Chú ý: bài này giống với LDS1 nhưng thời gian chạy sẽ bị giới hạn nhiều hơn, hãy tìm cách tối ưu để có thể vượt qua time limit!
Ví dụ:
Với arr = [4,5,1] thì đầu ra của LDS1(arr) = 2. Dãy giảm dài nhất là dãy [4,1] với chiều dài là 2.
Đầu vào/ Đầu ra:
- [Đầu vào] array of integers arr
1 <= arr.length() <= 100000 - [Đầu ra] integers
- Giới hạn thời gian chạy : 0.1s
Post Comment