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

Điểm: 0,04

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

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

Input: stdin

Output: stdout

Nguồn bài:

Dân gian

Dạng bài

Ngôn ngữ cho phép

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

Cho một dãy số nguyên gồm ~N~ phần tử ~A_1, A_2, \dots,A_N~.

Biết rằng dãy con tăng đơn điệu là ~1~ dãy ~A_{i_{1}}, \dots, A_{i_{k}}~ thỏa mãn ~i_{1} < i_{2} < \dots < i_{k}~ và ~A_{i_{1}} < A_{i_{2}} < \dots < A_{i_{k}}~. 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ử?

Input

Dòng ~1~ gồm ~1~ số nguyên là số ~N (1 \le N \le 1000)~.
Dòng thứ ~2~ ghi ~N~ số nguyên ~A_1, A_2, \dots, A_N (1 \le A_i \le 10000)~.

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Sample Input

6
1 2 5 4 6 2

Sample Output

Note

Dãy con dài nhất là dãy ~A_1 = 1 < A_2 = 2 < A_4 = 4 < A_5 = 6~, độ dài dãy này là ~4~.

Download test và solution tại đây.

Bình luận

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

-2

Tuandunglopa1 đã bình luận lúc 5, Tháng 4, 2024, 8:24

uoc duoc di

-14

nb_lehongphong_tranngocminh đã bình luận lúc 5, Tháng 1, 2024, 10:24

include <bits/stdc++.h>

pragma warning(disable:4996)

pragma warning(disable:6031)

pragma GCC optimize ("O3")

define CRTSECURENOWARNINGS_

define popb pop_back

define pushb push_back

define lb lower_bound

define ub upper_bound

define fi first

define se second

define be begin

define en end

define FASTER iosbase::syncwith_stdio(false);cin.tie(NULL);

typedef long long ll; typedef double db; typedef unsigned long long usll; typedef signed long long sll; const ll mod=1e9+7; const db pii=3.14; using namespace std; ll n,a[100005],b[1000005],vt,kq; //================================================ //================================================ int main() { FASTER; freopen("1.inp","r",stdin); freopen("1.out","w",stdout); cin>>n; for(long i=1;i<=n;i++) { cin>>a[i]; b[i]=2e9; } for(long i=1;i<=n;i++) { vt=lower_bound(b+1,b+n+1,a[i])-b; b[vt]=a[i]; kq=max(kq,vt); } cout<<kq<

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

-8

triclone_3 đã bình luận lúc 10, Tháng 12, 2023, 10:55

. . . Don't Coming Maybe| đố ai hiểu

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

0

apotocaplyse đã bình luận lúc 20, Tháng 2, 2024, 8:30

xàm

-11

playerno1 đã bình luận lúc 3, Tháng 12, 2023, 13:59

..

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

-19

asdsadsad đã bình luận lúc 6, Tháng 11, 2023, 16:12

bantumlum bantungtoe

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

-18

khoihk20 đã bình luận lúc 29, Tháng 9, 2023, 2:52

upvote bé với

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

-33

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.

-17

Tri đã bình luận lúc 19, Tháng 2, 2023, 5:41

test ổn ko

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

-19

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

Bài toán ví dụ khi mình mới học QHĐ nè

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

-27

avatarstar1133 đã bình luận lúc 29, Tháng 7, 2022, 10:10

bài này trùm khó

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

-23

Xcuad đã bình luận lúc 19, Tháng 6, 2022, 2:47

Test case bị sai rồi hay sao ấy

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

-23

flexity đã bình luận lúc 26, Tháng 5, 2022, 8:01

bài này test sai à ?

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

-13

hh123123 đã bình luận lúc 26, Tháng 5, 2022, 12:34

k

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

-46

HV_DuongPhucThienNhan_BL_2022 đã bình luận lúc 12, Tháng 1, 2022, 14:52

Quá đơn giản với python

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

-112

manhtuan22007 đã bình luận lúc 18, Tháng 7, 2021, 8:01

bủh bủh lmao

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

-53

DoanTungLamKoCopyCode đã bình luận lúc 31, Tháng 10, 2021, 11:42

noi bay

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

-163

dungp24 đã bình luận lúc 29, Tháng 5, 2021, 4:13 ← chỉnh sửa →

.

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