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

Khó

quy hoạch độngtìm kiếm nhị phân5 test · 3 giây

Cho dãy n số nguyên. Tìm độ dài dãy con tăng ngặt dài nhất (các phần tử giữ nguyên thứ tự nhưng không cần liền nhau).

DP O(n²) quá chậm với n = 2·10⁵. Cách O(n log n): duy trì mảng tails[k] = giá trị cuối nhỏ nhất của dãy tăng độ dài k + 1, cập nhật bằng tìm kiếm nhị phân.

Dữ liệu vào

Dòng 1: n (1 ≤ n ≤ 2·10⁵).

Dòng 2: n số nguyên (|aᵢ| ≤ 10⁹).

Độ dài dãy con tăng dài nhất.

Input

8
10 9 2 5 3 7 101 18

Output

Ví dụ 2, 3, 7, 101

Input

4
7 7 7 7

Output

Tăng ngặt nên chỉ được 1

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.