[Mảng 1 Chiều Cơ Bản]. Bài 48. Dãy con liên tiếp tăng dài nhất

Điểm: 1,00 (OI)

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

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

Input: stdin

Output: stdout

Tác giả:

28tech.com.vn

Nguồn bài:

28Tech

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng A[] gồm N phần tử nhiệm vụ của bạn là hãy liệt kê những dãy con liên tiếp tăng chặt dài nhất.

Gợi ý : So sánh a[i] và a[i - 1], nếu a[i] > a[i - 1] thì cập nhật độ dài dãy con hiện tại, ngược lại thì bạn so sánh độ dài dãy con kết thúc tại a[i - 1] so với kỷ lục đang có và cập nhật kết quả. Nếu độ dài dãy con đang có tốt hơn kỷ lục thì ghi nhận 1 dãy con, trường hợp độ dài dãy con hiện tại chỉ bằng dãy con kỷ lục thì tăng thêm 1 dãy con nữa. Nên dùng 1 mảng để lưu chỉ số bắt đầu của các dãy con thỏa mãn.

Đầu vào

• Dòng 1 là T : số bộ test

• Mỗi bộ test gồm 2 dòng

• Dòng 1 là N : số phần tử trong mảng

• Dòng 2 là N số trong mảng

Giới hạn

• 1<=T<=100

• 1<=N<=1000

• 0<=A[i]<=1000

Đầu ra

• Đối với mỗi bộ test dòng 1 in ra độ dài dãy con tăng chặt dài nhất, các dòng tiếp theo liệt kê các dãy con thỏa mãn trên từng dòng. Ngoài ra bạn cần ghi thêm số thứ tự bộ test. Xem test mẫu để rõ hơn yêu cầu.

Ví dụ :

Input 01

5
10
39 48 41 18 12 35 10 29 29 45 
10
19 37 14 24 49 45 36 25 38 16 
10
40 28 1 29 11 1 36 32 33 26 
10
13 32 1 18 49 7 48 1 17 32 
10
45 27 27 19 15 10 6 1 0 0

Output 01

Bình luận

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

0

nguyenmanhtriet đã bình luận lúc 26, Tháng 7, 2026, 13:11

Tóm tắt thuật toán:

Biến ban đầu: Cần 3 mảng toàn cục: a[] (lưu dữ liệu), vitribatdau[] (lưu index bắt đầu dãy), và dodai[] (lưu độ dài dãy).

Khởi tạo test: Xóa sạch 2 mảng lưu trữ bằng memset, đặt biến id = 0 (số thứ tự dãy) và max_len = 1 (kỷ lục dài nhất).

Duyệt mảng: Chạy vòng lặp duy nhất for (i = 0; i < n; i++) quét qua các phần tử.

Mở dãy mới: Nếu dodai[id] == 0, ghi nhận vitribatdau[id] = i và đặt do_dai[id] = 1.

Nối dài dãy: Nếu phần tử sau lớn hơn phần tử trước (a[i] < a[i+1]), tăng do_dai[id]++.

Cập nhật kỷ lục: Lập tức gán maxlen = dodai[id] nếu độ dài đoạn hiện tại lớn hơn max_len.

Chốt dãy: Nếu đoạn bị đứt (a[i] >= a[i+1]) hoặc chạy đến phần tử cuối cùng, chốt dãy bằng cách tăng id++ để đếm đoạn mới.

Kết thúc quét: Hoàn thành vòng lặp, ta đã có sẵn max_len và thông tin lưu trữ của mọi đoạn tăng để đem đi xử lý tiếp.

0
Hung123456 đã bình luận lúc 3, Tháng 7, 2026, 6:25
include <bits/stdc++.h>

using namespace std;

int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); int n,res; cin>>n; int d=n; int c=1; while(n--){ int b=d-n; cout<<"Test #"<<b<<" :"<<'\n'; int m; cin>>m; int a[m]; int sum=1; for (int i=0;i<m;i++){ cin>>a[i]; if (i>0){ if(a[i]-a[i-1]>0){ sum++; } else if (sum!=1&&a[i]-a[i-1]<=0){ if (sum>=c){ c=sum; } sum=1; } } } if (sum >= c) { c = sum; } if (c==1){ cout<<c<<'\n'; for (int i=0;i<m;i++){ cout<<a[i]<<'\n'; } } else{ cout<<c<<'\n';

} sum=1; for (int i=0;i<m;i++){ if (i>0){ if(a[i]-a[i-1]>0){ sum++; if (sum==2){ res=i-1; } } else if (sum!=1&&a[i]-a[i-1]<=0){ if(sum==c){ for (int j=res;j<sum+res;j++){ cout<<a[j]<<" "; } cout<<'\n'; } sum=1; } } } if (sum == c && c != 1) { for (int j = res; j < sum + res; j++) { cout << a[j] << " "; } cout << '\n'; } c=1; sum=1; cout<<'\n'; } return 0;

}

KieuQuangMinh đã bình luận lúc 4, Tháng 6, 2026, 16:17

include<bits/stdc++.h>

using namespace std;

int a[1005];

vector v;

int main(){

int q; cin >> q;
int cnt=0;
while(q--){
    v.clear();
    int n; cin >> n;
    for(int i=0;i&lt;n;i++) cin >> a[i];
    int dem=1;
    int kilucdem=0;
    int current_start=0,best_start=0;
    int best_end=0;
    for(int i=1;i&lt;n;i++){
        if(a[i]>a[i-1]){
            ++dem;
        }
        else{
            if(dem>kilucdem){
                kilucdem=dem;
                best_start=current_start;
                best_end=i-1;
                v.clear();
                vector<int> temp;
                for(int m=best_start;m<=best_end;m++){
                    temp.push_back(a[m]);
                }
                v.push_back(temp);
            }
            else if(dem==kilucdem){
                kilucdem=dem;
                best_start=current_start;
                best_end=i-1;
                vector<int> temp;
                for(int m=best_start;m<=best_end;m++){
                    temp.push_back(a[m]);
                }
                v.push_back(temp);
            }
            dem=1; current_start=i;
        }
    }
    if(dem>kilucdem){
        kilucdem=dem;
        best_start=current_start;
        best_end=n-1;
        v.clear();
        vector<int> tmp;
        for(int h=best_start;h<=best_end;h++){
            tmp.push_back(a[h]);
        }
        v.push_back(tmp);
    }
    else if(dem==kilucdem){
        kilucdem=dem;
        best_start=current_start;
        best_end=n-1;
        vector<int> tmp;
        for(int h=best_start;h<=best_end;h++){
            tmp.push_back(a[h]);
        }
        v.push_back(tmp);
    }
    cout << "Test #" << ++cnt << " :\n";
    cout << kilucdem << "\n";
    for(const auto &x:v){
        for(int j:x){
            cout << j << " ";
        }
        cout << "\n";
    }
}
return 0;

} cho ae quả code rảnh rỗi =))

huhuhahaha đã bình luận lúc 25, Tháng 3, 2026, 14:02

Full AC:

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

int main() {
    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        int n; cin >> n;
        vector<int> a(n);
        for (int &x : a) cin >> x;

        int maxLen = 1, len = 1;
        vector<int> start;

        for (int i = 1; i < n; i++) {
            if (a[i] > a[i - 1]) len++;
            else {
                if (len > maxLen) {
                    maxLen = len;
                    start.clear();
                    start.push_back(i - len);
                } else if (len == maxLen) {
                    start.push_back(i - len);
                }
                len = 1;
            }
        }

        // đoạn cuối
        if (len > maxLen) {
            maxLen = len;
            start.clear();
            start.push_back(n - len);
        } else if (len == maxLen) {
            start.push_back(n - len);
        }

        cout << "Test #" << t << " :\n";
        cout << maxLen << endl;

        if (maxLen == 1) {
            for (int x : a)
                cout << x << " \n";
        } else {
            for (int st : start) {
                for (int i = st; i < st + maxLen; i++)
                    cout << a[i] << " ";
                cout << endl;
            }
        }
    }
}

kietne đã bình luận lúc 29, Tháng 12, 2025, 12:48

include <bits/stdc++.h>

using namespace std; using ll = long long;

int DEM = 1;

void run_case() { int n; if (!(cin >> n)) return; vector<int> a(n); for (int &x : a) cin >> x;

int bestLen = 1;
int curLen = 1;
int start = 0;
vector<int> pos; // lưu các start của đoạn có độ dài bestLen

for (int i = 1; i < n; ++i)
{
    if (a[i] > a[i - 1])
    {
        // tiếp tục đoạn tăng
        curLen++;
    }
    else
    {
        // kết thúc đoạn tăng hiện tại [start, i-1]
        if (curLen > bestLen)
        {
            bestLen = curLen;
            pos.clear();
            pos.push_back(start);
        }
        else if (curLen == bestLen)
        {
            pos.push_back(start);
        }
        // bắt đầu đoạn mới tại i
        curLen = 1;
        start = i;
    }
}

// xử lý đoạn cuối (mảng có thể kết thúc bằng đoạn tăng)
if (curLen > 0)
{
    if (curLen > bestLen)
    {
        bestLen = curLen;
        pos.clear();
        pos.push_back(start);
    }
    else if (curLen == bestLen)
    {
        pos.push_back(start);
    }
}

// Nếu n == 0 (không có phần tử) hoặc không có đoạn tăng (n>=1 thì bestLen>=1)
cout << "Test #" << DEM << " :\n";
cout << bestLen << "\n";
for (int s : pos)
{
    for (int k = 0; k < bestLen; ++k)
    {
        if (k)
            cout << ' ';
        cout << a[s + k];
    }
    cout << '\n';
}
DEM++;

}

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

int t;
if (!(cin >> t))
    return 0;
while (t--)
    run_case();
return 0;

}

bengokyeuanh99 đã bình luận lúc 23, Tháng 6, 2025, 18:16 ← chỉnh sửa →

include <stdio.h>

int a[1005], pos[1005];

int main() { int T, n; scanf("%d", &T); for (int t = 1; t <= T; ++t) { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    int maxLen = 1;
    int len = 1;
    int start = 0;
    int cnt = 0;
    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i - 1]) {
            ++len;
        } else {
            if (len > maxLen) {
                maxLen = len;
                cnt = 0;
                pos[cnt++] = start;
            } else if (len == maxLen) {
                pos[cnt++] = start;
            }
            len = 1;
            start = i;
        }
    }
    if (len > maxLen) {
        maxLen = len;
        cnt = 1;
        pos[0] = start;
    } else if (len == maxLen) {
        pos[cnt++] = start;
    }
    printf("Test #%d :\n", t);
    printf("%d\n", maxLen);
    for (int i = 0; i < cnt; ++i) {
        int s = pos[i];
        for (int j = 0; j < maxLen; ++j)
            printf("%d ", a[s + j]);
        printf("\n");
    }
}
return 0;

}

ThangPX đã bình luận lúc 31, Tháng 3, 2025, 8:52

include <bits/stdc++.h>

using namespace std;

void solve(int x) { int n; cin >> n; vector<int> A(n); for (int &x : A) { cin >> x; }

int max_count = 1, current_count = 1, start_index = 0;
vector<vector<int>> b;

for (int i = 1; i < n; i++) {
    if (A[i] > A[i - 1]) {
        current_count++;
    } else {
        if (current_count > max_count) {
            max_count = current_count;
            b.clear();
        }

        if (current_count == max_count) {
            b.push_back(vector<int>(A.begin() + start_index, A.begin() + i));
        }

        current_count = 1;
        start_index = i;
    }
}

if (current_count > max_count) {
    max_count = current_count;
    b.clear();
}

if (current_count == max_count) {
    b.push_back(vector<int>(A.begin() + start_index, A.end()));
}

cout << "Test #" << x << " :\n";
cout << max_count << '\n';

for (const auto &seq : b) {
    for (int num : seq) {
        cout << num << " ";
    }

    cout << '\n';
}

}

int main() { int T; cin >> T;

for (int i = 1; i <= T; i++) {
    solve(i);
}

return 0;

}

tranthuyvan đã bình luận lúc 4, Tháng 2, 2025, 15:04

include <iostream>

using namespace std; const int N=100+5; int a[N],s[N]; int T,n; int main() { cin>>T;

for(int t=1;t<=T;t++) {
    cin>>n;
    for(int i=0;i&lt;n;i++) cin>>a[i];
    int max=1,D=1,c=0;
    for (int i=1;i&lt;n;i++) {
        if(a[i]>a[i-1]) D++;
        else {
            if (D>max) {
                max=D;
                c=0;
                s[c]=i-D;
                c++;
            }
            else if (D==max) {
                s[c]=i-D;
                c++;
            }
            D=1; }}
    if (D>max) {
        max=D;
        c=0;
        s[c]=n-D;
        c++;
    }
    else if (D==max) {
        s[c]=n-D;
        c++;
    }
    cout<<"Test #"<&lt;t<<":\n"<<max<<endl;
    for (int i=0;i&lt;c;i++) {
        for (int j=s[i];j&lt;s[i]+max;j++) cout<&lt;a[j]<<" ";
        cout<&lt;endl;}}
return 0;

}

giúp mình với

-6

perkbevis2k4 đã bình luận lúc 24, Tháng 11, 2024, 5:36

Ai muốn tham khảo code thì vô github: perk bevis nha

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

-2

BaoHuangg đã bình luận lúc 12, Tháng 3, 2025, 10:06

xin link a

-2

tuyen_pham đã bình luận lúc 25, Tháng 10, 2024, 14:12

include <bits/stdc++.h>

using namespace std; int n,a[1000000]; vector<int>b; int main() { int t; cin>>t; int k=1; while(t--) { cin>>n; for(int i=0; i<n; i++) cin>>a[i]; int dem=1,m=0; for(int i=0; i<n; i++) { if(a[i]<a[i+1]) dem++; else { m=max(m,dem); dem=1; } } cout<<"Test #"<<k<<" :"<<endl;k++; cout<<m<

-2

luan54bc đã bình luận lúc 22, Tháng 8, 2024, 13:37

include <bits/stdc++.h>

using namespace std;

bool nt(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; }

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

int dem = 0, vt = 0, kiluc = 0;
for (int i = 0; i < n; i++) {
    if (nt(a[i])) {
        dem++;
        if (dem > kiluc) {
            kiluc = dem;
            vt = i - dem + 1;
        }
    } else {
        dem = 0;
    }
}

if (kiluc == 0) {
    cout << "NOT FOUND" << endl;
} else {
    cout << kiluc << endl;
    for (int i = vt; i < vt + kiluc; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

return 0;

} bai nay em dan sai bai nay cua 46 a

-5

Hahaaaa đã bình luận lúc 11, Tháng 7, 2024, 4:40

include <bits/stdc++.h>

using namespace std; void test(){int n;cin>>n;vector<int> a(n);vector b;string s="";for(int&i:a){cin>>i;}s+=tostring(a[0])+' ';int tmp=1,maxx=0;for(int i=1;i<n;i++){if(a[i]>a[i-1]){s+=tostring(a[i])+' ';tmp++;}else{b.pushback({s,tmp});s.clear();s+=tostring(a[i])+' ';if(tmp>maxx){maxx=tmp;}tmp=1;}if(i==n-1){b.push_back({s,tmp});}}cout<>t;int x=1;while(t--){cout<<"Test #"<<x++<<" :"<<endl;test();}} mọi người cho em hỏi em bị sai ở đâu với ạ, vẫn có testcase bị sai ạ.

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

-4

NTH11112222 đã bình luận lúc 11, Tháng 6, 2024, 13:43

include <bits/stdc++.h>

using namespace std; void xuat(vector<int>& subseq) { for (int num : subseq) { cout << num << " "; } cout << endl; } int main() { int T; cin >> T; for (int t = 1; t <= T; ++t) { int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } int maxlen = 0; vector allsubseq; vector<int> subseq; for (int i = 0; i < N; ++i) { if (i == 0 || A[i] > A[i - 1]) { subseq.pushback(A[i]); } else { if (subseq.size() >= maxlen) { if (subseq.size() > maxlen) { allsubseq.clear(); maxlen = subseq.size(); } allsubseq.pushback(subseq); } subseq.clear(); subseq.pushback(A[i]); } } if (subseq.size() >= maxlen) { if (subseq.size() > maxlen) { allsubseq.clear(); maxlen = subseq.size(); } allsubseq.pushback(subseq); } cout << "Test #" << t << " :\n"; cout << maxlen << endl; for (vector<int>& seq : allsubseq) { xuat(seq); } } return 0; } Bài giải chỉ mang tính chất tham khảo cho những ai chưa biết làm nhé!