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.

-6

phamvuhoang486 đã bình luận lúc 17, Tháng 11, 2024, 13:39

Dồ Ái Mồ

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

-6
nq_tthcsttnq_trinhbaotrung đã bình luận lúc 14, Tháng 11, 2024, 13:48
include <iostream>

include <vector>

include <algorithm>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) { vector<int> sub; for (int x : nums) { auto it = lowerbound(sub.begin(), sub.end(), x); if (it == sub.end()) { sub.pushback(x); } else { *it = x; } } return sub.size(); }

int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; }

cout << longestIncreasingSubsequence(nums) << endl; return 0;

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

4

ChiPhatNguyen đã bình luận lúc 12, Tháng 1, 2025, 13:24

chatgpt ?

-8

_haine đã bình luận lúc 26, Tháng 10, 2024, 9:55

bai nay de vai lon

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

-6

dingu đã bình luận lúc 26, Tháng 10, 2024, 9:56

xam v ba

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

-4

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

-13

nb_truonghansieu_legiabao đã bình luận lúc 1, Tháng 8, 2024, 14:34

bài này dễ vc

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

-3

PhoDP đã bình luận lúc 16, Tháng 6, 2024, 12:26

Quy Hoạch Động kiểu trước mắt ta mọi thứ đều hạ đẳng mình ta thưởng đẳng -Tôi kiểu A Long

-10

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

uoc duoc di

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

-25

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<<endl return> </endl>

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

-20

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.

-5

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

xàm

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

-14

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.

-31

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.

-35

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.

-55

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.

-20

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.

-25

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.

-31

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.

-27

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.

-27

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.

-17

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.

-56

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.

-128

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.

-62

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.

-184

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.