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

    Cho một dãy gồm nnn số nguyên. Một dãy con tăng là dãy thu được bằng cách xoá bớt (có thể không xoá) một số phần tử mà vẫn giữ nguyên thứ tự, sao cho các phần tử còn lại tăng nghiêm ngặt (phần tử sau lớn hơn hẳn phần tử trước).

    Hãy tìm độ dài của dãy con tăng dài nhất.

    Với ràng buộc nnn lớn, cần thuật toán hiệu quả O(nlog⁡n)O(n \log n)O(nlogn) (kết hợp quy hoạch động với tìm kiếm nhị phân) thay vì O(n2)O(n^2)O(n2).

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

      Dòng đầu chứa số nguyên nnn. Dòng thứ hai chứa nnn số nguyên cách nhau bởi dấu cách.

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

      1≤n≤2⋅1051 \le n \le 2 \cdot 10^51≤n≤2⋅105; −109≤ai≤109-10^9 \le a_i \le 10^9−109≤ai​≤109.

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

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

    Ví dụ:

    Đầu vào:

    6
3 1 4 1 5 9

    Đầu ra:

    4

    Giải thích:

    Một dãy con tăng dài nhất là 1, 4, 5, 9 (độ dài 4); 3,4,5,9 cũng độ dài 4.

    Đang tải editor...