Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Dãy con tăng dài nhất (LIS)

    Cho dãy nnn số nguyên. Tìm độ dài dãy con tăng ngặt dài nhất (LIS). Yêu cầu thuật toán O(nlog⁡n)O(n \log n)O(nlogn).

    • Định dạng đầu vào:

      Dòng đầu nnn. Dòng hai gồm nnn số nguyên.

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105, ∣ai∣≤109|a_i| \le 10^9∣ai​∣≤109.

    • Định dạng đầu ra:

      In một số nguyên: độ dài LIS.

    Ví dụ:

    Đầu vào:

    6
1 3 2 4 3 5

    Đầu ra:

    4

    Giải thích:

    Một LIS là 1,2,4,5 (hoặc 1,3,4,5) độ dài 4.

    Đang tải editor...