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

Điểm: 0,05 (OI)

Giới hạn thời gian: 0.3s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Bài cổ điển

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

(Giống bài LIQ) Cho một dãy gồm ~N~ số nguyên (~1~ ~\leq~ ~N~ ~\leq~ ~30000~). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.

Input

Dòng đầu tiên gồm số nguyên ~N~.
Dòng thứ hai gồm ~N~ số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán

Sample Input

5
2 1 4 3 5

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

nguyendailam0719 đã bình luận lúc 7, Tháng 1, 2026, 13:16 ← sửa 2 →

Spoil mạnh nha

Ko nên xem đến cuối

lis dùng để lưu đuôi nhỏ nhất của dãy tăng độ dài k

Với mỗi x: tìm vị trí bằng lowerbound nếu chưa có → pushback có rồi → thay thế

Cuối cùng lis.size() chính là độ dài LIS

>

!#include <bits/stdc++.h> using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> lis; for (int x : a) { auto it = lowerbound(lis.begin(), lis.end(), x); if (it == lis.end()) lis.pushback(x); else *it = x; } cout << lis.size(); return 0; }

0

vuonghoaitamdz9 đã bình luận lúc 14, Tháng 11, 2025, 11:43 ← chỉnh sửa →

Spoil dùng segment

Sử dụng segment lưu vị trí tốt nhất

Code tại đây https://ide.usaco.guide/Oe14VyxxjEdKtKCr8bY

vominhmanh10 đã bình luận lúc 30, Tháng 10, 2025, 12:58

triển khai với tìm kiếm nhị phân

import bisect as bs
n = int(input())
a = list(map(int, input().split()))
lis = []
for x in a:
    i = bs.bisect_left(lis, x)
    if i >= len(lis): lis.append(x)
    else: lis[i] = x
print(len(lis))

-13

LVT_K66_TRANDUYBAO đã bình luận lúc 12, Tháng 10, 2025, 16:51

ước downvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-1

namta1082012 đã bình luận lúc 26, Tháng 9, 2025, 14:22

Spoiler:

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<long long> lis; for (long long x : a) { auto it = lowerbound(lis.begin(), lis.end(), x); if (it == lis.end()) lis.pushback(x); else *it = x; } cout << lis.size() << "\n"; return 0; }

-21

vutuankiet đã bình luận lúc 29, Tháng 6, 2025, 5:23

xin downvite

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-21

chuthang050520008 đã bình luận lúc 2, Tháng 12, 2024, 7:16

def timkiem(a,x): l, r = 0 , len(a) - 1 while l <= r: m = (l + r) // 2 if a[m] < x: l = m + 1 else: r = m - 1 return l n = int(input()) a = list(map(int,input().split())) L =[] for x in a: p = timkiem(L,x) if p == len(L): L.append(x) else: L[p] = x print(L) print(len(L))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-24

ducbaothan đã bình luận lúc 15, Tháng 10, 2024, 12:25 ← sửa 3 →

https://ideone.com/AHw0DY

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-32

khiemgia1105 đã bình luận lúc 4, Tháng 10, 2024, 7:47

Mn đăng kí khoắ học ở prf mình nhé, cam kết có giải

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-25

vuongbankien012 đã bình luận lúc 3, Tháng 9, 2024, 5:48

ai vote up tui tui tang Yuki Suo ngoai doi cho

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-11

nongquan đã bình luận lúc 11, Tháng 7, 2024, 4:13 ← sửa 2 →

Ý tưởng : lấy từ anh yugihacker thuật toán : tham lam + tknp độ phức tạp : O(n.logn) mình sẽ tạo thêm mang f với f[i]: phần tử cuối nhỏ nhất của dãy con độ dài i khi đó độ dài mảng f là kq bài toán ta tham lam ở chỗ có nhiều dãy con độ dài i nhưng ta sẽ lấy dãy có ptu kết thúc nhỏ nhất để tối ưu bài toán khi chọn thêm phần tử để thêm vào dãy đó ta thấy mảng f là mảng tăng dần để chứng minh nó đúng ta sẽ chứng minh ngược lại của nó là sai Ví dụ : f[1] = 3 và f[2] = 2 mà theo quy tắc tham lam ở trên thì dãy con độ dài 1 kia phải lấy ptu gtri là 2 để tối ưu chứ k lưu giá trị 3 như ví dụ và ta có thể thêm ptu gtri 3 kia vào dãy con độ dài 2 kia để tạo thành dãy con có độ dài là 3 kết thúc là 3 vì mảng f tăng dần nên ta được phép tknp trong mảng f Duyệt từng phần tử mảng a rồi tknp phần tử có giá trị lớn hơn hoặc bằng a[i] gọi k là vị trí ptu đó trong mảng f thì ta có thể thêm ptu a[i] vào dãy con độ dài k-1 vì ptu kết thúc của dãy độ dài k-1 nhỏ hơn a[i] khi đó nó tạo thành dãy con độ dài k ptu kết thúc là a[i]

include<bits/stdc++.h>

define ll long long

using namespace std; ll n, a[100003], f[100003], maxn = 1;

int main() { cin>>n; for (int i = 1; i <= n; i++) { cin>>a[i]; } f[1] = a[1]; for (int i = 2; i <= n; i++) { ll k = lower_bound(f+1, f+maxn+1, a[i])-f; f[k] = a[i]; maxn = max(maxn, k); } cout<<maxn; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-20

vietanhnrosv2 đã bình luận lúc 2, Tháng 7, 2024, 16:39 ← sửa 13 →

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-11

trongnghia đã bình luận lúc 12, Tháng 6, 2024, 11:23

bài này khó thiệt nha =))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-13

nhanphamj đã bình luận lúc 8, Tháng 6, 2024, 7:52

đơn giản

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

12

lenguyenminhkhang2b đã bình luận lúc 22, Tháng 4, 2024, 13:54

Mọi người cho mình hỏi là bài này có bản in ra dãy con không do mình học thấy có bài nhx ko có test nên mình hỏi. Mong mọi người giúp đỡ ạ. Cảm ơn mọi người nhiều ! =)) Đừng down vote mình nha

-6

Le_peace đã bình luận lúc 25, Tháng 4, 2024, 6:54

khong ban nhe

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-13

thaihong7577 đã bình luận lúc 22, Tháng 4, 2024, 5:25

Spoil!

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

37

YugiHackerKhongCopCode đã bình luận lúc 21, Tháng 3, 2024, 16:47

Spoil!

Cách 1: Quy hoạch động + Tìm kiếm nhị phân

Gọi mảng ~b~ : ~b_i~ là giá trị nhỏ nhất của phần tử cuối trong tất cả các dãy con tăng độ dài ~i~

Mảng ~b~ là một dãy không giảm (~b_i \le b_{i+1}~ với mọi ~i~)

Để tìm độ dài dãy con tăng dài nhất kết thúc tại vị trí ~a_i~, ta tìm ra vị trí ~j~ lớn nhất thoả mãn ~b_j \le a_i~, như vậy ta có thể tạo ra một dãy con tăng độ dài ~j+1~

Do mảng ~b~ không giảm, dễ dàng tìm kiếm được vị trí ~j~ lớn nhất bằng tìm kiếm nhị phân

Độ phức tạp ~O(n \cdot logn)~

Link video solution: Dãy Con Tăng Dài Nhất sử dụng Tìm Kiếm Nhị Phân

Cách 2: Quy hoạch động + Segment tree hoặc Fenwick Tree (update sau)

-5

nguyenthiennhan17 đã bình luận lúc 20, Tháng 6, 2024, 9:27 ← chỉnh sửa →

Không có th bi = bi + 1 anh ạ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-55

vendettas đã bình luận lúc 17, Tháng 2, 2024, 6:07

khi bạn deo nhắn gì sai nhưng vẫn bị downvote <(")

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-40

KiraYoshikage đã bình luận lúc 2, Tháng 2, 2024, 15:33

ai hỏi?

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

24

triclone_3 đã bình luận lúc 8, Tháng 11, 2023, 4:15 ← sửa 4 →

Các bạn xem thì ủng hộ mình 1 down vote, mình cảm ơn! Bài này thì các bạn nên sử dụng multiset để các phần tử giống nhau sẽ không bị xoá.

Đầu tiên nhập vào một số n

Sau đó nhập n số vào cho hết chúng vào multiset.

Tiếp theo dùng hàm lower_bound() để tìm m là vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng với giá trị chỉ định.

Rồi kiểm tra xem nều m != multiset.end() thì xoá m đi. Code mẫu (C++) tại Đây

5

kietjumper đã bình luận lúc 31, Tháng 10, 2024, 1:50

Sao lại ủng hộ 1 downvote? =))

-47

huynhquocluatit10 đã bình luận lúc 15, Tháng 10, 2023, 12:46

Thanh Phong deptrai nhat the gioi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-79

giataino đã bình luận lúc 14, Tháng 10, 2023, 9:26

d!t me bai nhon lu

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-56

nhan19042007 đã bình luận lúc 12, Tháng 10, 2023, 6:53 ← sửa 2 →

bài này mình lỡ cmt mà ko biết xóa cmt sao xin mn đừng downvote em ạ :((

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-109

nthquan_1505 đã bình luận lúc 30, Tháng 3, 2023, 4:22

xin downvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-49

maintainit đã bình luận lúc 21, Tháng 2, 2023, 14:17

mik ga vl nghi deo ra

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-25

harmxvu đã bình luận lúc 24, Tháng 6, 2023, 13:15

dùng quy hoạch động bạn

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-37

boneman23 đã bình luận lúc 8, Tháng 1, 2023, 9:47

hình như giống bản dễ nhỉ?

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-28

MaiThanh1342 đã bình luận lúc 9, Tháng 1, 2023, 8:54

quan trong la thoi gian thuc thi thoi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-37

lkva2019 đã bình luận lúc 7, Tháng 1, 2023, 9:00

kho qua ae :o

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-19

maintainit đã bình luận lúc 21, Tháng 2, 2023, 14:19

uk

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-25

thanh20092007 đã bình luận lúc 28, Tháng 8, 2022, 3:31

kho the nho

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

22

minhducle31o đã bình luận lúc 19, Tháng 4, 2023, 9:09

bạn cố gắng là làm được mà. cố lên!!!

-10

codelozd đã bình luận lúc 9, Tháng 2, 2024, 8:37

oke ban

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-158

modwwe đã bình luận lúc 11, Tháng 7, 2022, 17:18

bài dễ vl

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-20

minhducle31o đã bình luận lúc 19, Tháng 4, 2023, 9:09

bạn nên xem lại ngôn ngữ của mình

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-11

codelozd đã bình luận lúc 9, Tháng 2, 2024, 8:39

oke ban

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

22

kennikai đã bình luận lúc 31, Tháng 12, 2021, 5:04 ← sửa 2 →

bài này làm thấm phết!