Question

 Dãy con của một dãy là dãy có thể đạt được bằng cách xoá đi một số phần tử trong dãy ban đầu. Dãy rỗng và dãy ban đầu cũng là dãy con của dãy ban đầu. Bài toán tìm một dãy con tăng dài nhất trong một tập các phần tử là tìm một dãy con của dãy ban đầu sao cho trong dãy con này phần tử đứng sau lớn hơn hẵn phần tử đứng trước. Dãy con này không cần thiết phải liền kề, hoặc là duy nhất.

     Bài toán dãy con tăng dài nhất được áp dụng rộng rãi ở nhiều lĩnh vực: Toán học (thuật toán, lý thuyết ma trận, lý thuyết đại diện) hay Vật Lý. Trong bài tập này nhiệm vụ của bạn cần thực hiện là viết chương trình nhận đầu vào là một dãy số nguyên có N phần tử A1, A2, ..., An, tìm dãy con tăng dài nhất của dãy đã cho.

Dữ liệu nhập:

  - Dòng đầu tiên là số nguyên dương N (1 ≤ N ≤ 5.000)

  - Dòng thứ hai chứa N số nguyên thuộc dãy A. (|Ai| ≤ 10⁹ Với i=1..N)

Kết quả:

  - Ghi ra một số nguyên là độ dài dãy con tăng dài nhất tìm được.

Ví dụ

input

5
1 1 3 4 1

output

3                                                                         

 Giúp ạ

Answer 1

n = int(input())
a = list(map(int, input().split()))

dp = [a[0]] 

for i in range(1, n):
     left, right = 0, len(dp) - 1
    pos = len(dp)
    while left <= right:
        mid = (left + right) // 2
        if dp[mid] < a[i]:
            left = mid + 1
        else:
            pos = mid
            right = mid - 1
        if pos == len(dp):
        dp.append(a[i])
      else:
        dp[pos] = a[i]

print(len(dp))