Dãy con tăng dài nhất (bản khó)

Tác giả:

Dạng bài

Điểm: 400 (p) Thời gian: 0.2s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).

Test 1

Input

6
1 2 5 4 6 2

Output

Bình luận

0

Viet_osu 8:05 p.m. 27 Tháng 7, 2024

bạn làm bằng quy hoạch động có thể sẽ tle nha , có thể dùng tìm kiếm nhị phân giảm xuống còn O(n log n)