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

Please read the guidelines before commenting.

-4

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

Dồ Ái Mồ

-6
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.

2

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

chatgpt ?

-7

_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.

-5

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.

-3

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

-12

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.

-1

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

-9

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.

-25

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

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

-20

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.

-5

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.

-14

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

..

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

-31

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.

-34

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.

-53

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.

-20

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.

-25

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.

-31

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.

-27

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.

-27

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.

-17

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

k

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

-56

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.

-128

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.

-62

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.

-184

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

.

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