Đoàn tàu tăng tốc dài nhất

Binary-search Buổi 21 — DP 1D cổ điển Buổi 22 — DP 2D & LIS Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions

Dãy con tăng dài nhất (LIS)

Cho mảng gồm $N$ số nguyên $a_1, a_2, \dots, a_N$.

Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất. Dãy con của một mảng là một dãy thu được bằng cách xóa đi một số phần tử (hoặc không xóa phần tử nào) mà không làm thay đổi thứ tự tương đối của các phần tử còn lại.

Dữ liệu vào

  • Dòng 1: Số nguyên dương $N$ ($1 \le N \le 10^5$).
  • Dòng 2: $N$ số nguyên cách nhau bởi dấu cách ($-10^9 \le a_i \le 10^9$).

Dữ liệu ra

In ra một số nguyên duy nhất là độ dài của dãy con tăng nghiêm ngặt dài nhất.

Draft saved