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

Points: 0.04

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

Dân gian

Problem type

Allowed languages

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.

Comments

Comments

Please read the guidelines before commenting.

0

tien_phat commented on Jan. 27, 2026, 1:35 a.m.

include <bits/stdc++.h>

//#define FOR(i, a, b) for (int i = a; i < b; i++);

using namespace std;

int main() { int N; cin >> N; vector <int> A(N); for (int i = 0; i < N; i++) cin >> A[i]; vector <int> L(N, 1); for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) if (A[i] > A[j]) L[i] = max(L[i], L[j] + 1); cout << *max_element(L.begin(), L.end()); return 0; }

0

hanguyen140210 commented on Jan. 6, 2026, 7:16 a.m.

include<bits/stdc++.h>

using namespace std;

define vec vector

define ps push_back

int main(){ iosbase::syncwithstdio(0); cin.tie(0);cout.tie(0); // freopen("LIS.INP","r",stdin); // freopen("LIS.OUT","w",stdout); int n;cin>>n; vec<int>a(n); for(int&x:a)cin>>x; vec<int>b; for(auto&x:a){ auto it=lowerbound(b.begin(),b.end(),x); if(it==b.end())b.ps(x); else *it=x; } cout<<b.size(); }

vominhmanh10 commented on Oct. 30, 2025, 11:57 a.m.

ý là phiên bản tối ưu gọn hơ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))

-10

LVT_K66_TRANDUYBAO commented on Oct. 12, 2025, 4:51 p.m.

ước downvote

This comment is hidden due to too much negative feedback. Show it anyway.

-25

vutuankiet commented on June 29, 2025, 5:22 a.m.

xin downvote

This comment is hidden due to too much negative feedback. Show it anyway.

-24

phamvuhoang486 commented on Nov. 17, 2024, 1:39 p.m.

Dồ Ái Mồ

This comment is hidden due to too much negative feedback. Show it anyway.

-24
nq_tthcsttnq_trinhbaotrung commented on Nov. 14, 2024, 1:48 p.m.
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;

}
This comment is hidden due to too much negative feedback. Show it anyway.

18

ChiPhatNguyen commented on Jan. 12, 2025, 1:24 p.m.

chatgpt ?

-1

nvhuyen20236 commented on July 4, 2025, 3:09 p.m.

100%

-24

_haine commented on Oct. 26, 2024, 9:55 a.m.

bai nay de vai lon

This comment is hidden due to too much negative feedback. Show it anyway.

-9

dingu commented on Oct. 26, 2024, 9:56 a.m.

xam v ba

This comment is hidden due to too much negative feedback. Show it anyway.

-15

khiemgia1105 commented on Oct. 4, 2024, 7:47 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-22

nb_truonghansieu_legiabao commented on Aug. 1, 2024, 2:34 p.m.

bài này dễ vc

This comment is hidden due to too much negative feedback. Show it anyway.

-11

PhoDP commented on June 16, 2024, 12:26 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-18

Tuandunglopa1 commented on April 5, 2024, 8:24 a.m.

uoc duoc di

This comment is hidden due to too much negative feedback. Show it anyway.

-32

nb_lehongphong_tranngocminh commented on Jan. 5, 2024, 10:24 a.m.

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 0; } //█▀▀ █▀█ █▀▄ █▀▀ █▄▄ █▄█ █▀▄▀█ █ █▄░█ █░█ //█▄▄ █▄█ █▄▀ ██▄ █▄█ ░█░ █░▀░█ █ █░▀█ █▀█

This comment is hidden due to too much negative feedback. Show it anyway.

-30

triclone_3 commented on Dec. 10, 2023, 10:55 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-7

apotocaplyse commented on Feb. 20, 2024, 8:30 a.m.

xàm

This comment is hidden due to too much negative feedback. Show it anyway.

-16

playerno1 commented on Dec. 3, 2023, 1:59 p.m.

..

This comment is hidden due to too much negative feedback. Show it anyway.

-36

asdsadsad commented on Nov. 6, 2023, 4:12 p.m.

bantumlum bantungtoe

This comment is hidden due to too much negative feedback. Show it anyway.

-43

khoihk20 commented on Sept. 29, 2023, 2:52 a.m.

upvote bé với

This comment is hidden due to too much negative feedback. Show it anyway.

-66

nthquan_1505 commented on March 30, 2023, 4:22 a.m.

xin downvote

This comment is hidden due to too much negative feedback. Show it anyway.

-22

Tri commented on Feb. 19, 2023, 5:41 a.m.

test ổn ko

This comment is hidden due to too much negative feedback. Show it anyway.

-28

MaiThanh1342 commented on Jan. 8, 2023, 8:39 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-36

avatarstar1133 commented on July 29, 2022, 10:10 a.m.

bài này trùm khó

This comment is hidden due to too much negative feedback. Show it anyway.

-32

Xcuad commented on June 19, 2022, 2:47 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-32

flexity commented on May 26, 2022, 8:01 a.m.

bài này test sai à ?

This comment is hidden due to too much negative feedback. Show it anyway.

-19

hh123123 commented on May 26, 2022, 12:34 p.m.

k

This comment is hidden due to too much negative feedback. Show it anyway.

-61

HV_DuongPhucThienNhan_BL_2022 commented on Jan. 12, 2022, 2:52 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-136

manhtuan22007 commented on July 18, 2021, 8:01 a.m.

bủh bủh lmao

This comment is hidden due to too much negative feedback. Show it anyway.

-67

DoanTungLamKoCopyCode commented on Oct. 31, 2021, 11:42 a.m.

noi bay

This comment is hidden due to too much negative feedback. Show it anyway.

-195

dungp24 commented on May 29, 2021, 4:13 a.m. ← edited →

.

This comment is hidden due to too much negative feedback. Show it anyway.