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

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho một dãy số nguyên gồm ~N~ phần tử ~a_1, a_2, …, a_N~. Một dãy con đơn điệu tăng của dãy trên là dãy ~a_{i_1}, a_{i_2}, …, a_{i_k}~ sao cho: ~i_1 < i_2 < … < i_k~ và ~a_{i_1} < a_{i_2} < … < a_{i_k}~. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?

Input

  • Dòng đầu chứa số nguyên dương ~N~;
  • Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, …, a_N~, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

  • ~1 ≤ n ≤ 1000, -10^9 ≤ a_i ≤ 10^9~

Output

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

Sample

Input #1
6
1 2 5 4 6 2
Output #1
4

Hint

Giải thích #1:

  • Dãy con tăng dài nhất là dãy ~1, 2, 4, 6~ độ dài dãy này là ~4~.

Problem source: Chuyên Sơn La Online Judge

Bình luận

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


  • 0
    tienphat2101  đã bình luận lúc 28, Tháng 3, 2024, 3:14

    include <bits/stdc++.h>

    using namespace std;
int main(){
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i&lt;n;i++) cin >> a[i];
vector<int> L(n,1);
for(int i=0;i&lt;n;i++){
    for(int j=0;j&lt;i;j++){
        if(a[i]>a[j]){
            L[i]=max(L[j]+1,L[i]);
        }
    }
}
cout << *max_element(L.begin(),L.end());
}

    Code full AC nhé mọi người, cái này là dùng quy hoạch động, độ phức tạp của code này là O(n^2) nhưng vì đây là bản dễ nên vẫn AC.


  • 0
    hz001  đã bình luận lúc 16, Tháng 2, 2024, 1:45

    Blockquote

    include<bits/stdc++.h>

    using namespace std; using ll=long long; // int main(){ int n; ll a[1001]; cin>>n; vector<int> l(n,1); for(int i=0;i<n;i++) cin>>a[i]; 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())<<endl;; return 0; }


  • 0
    hieugiangho2015  đã bình luận lúc 10, Tháng 2, 2024, 15:00

    include <bits/stdc++.h>

    using namespace std;

    void sol(long long a[], long long n){ int l[100000]={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 ); } } } int MAX = INTMIN; for(int i = 0; i<n; i++){ if(l[i]>MAX){ MAX = l[i]; } } cout<<MAX; } int main(){ iosbase::syncwithstdio(false); cin.tie(NULL); long long a[100002]; long long n; cin>>n; for(int i=0; i<n; i++){ cin>>a[i]; } sol(a,n); return 0; }


  • 1
    Shit  đã bình luận lúc 9, Tháng 2, 2024, 7:26

    day so: 1 2 5 4 5 6 Vi tri: 0 1 2 3 4 5 day so khi sort: 1 2 4 5 5 6 Vi tri khi sort: 0 1 3 2 4 5 taa thay khi sort a[i1]<a[i2] nhung vi tri lai nguoc lai vi vay ta se dem xoi


  • 1
    thh  đã bình luận lúc 23, Tháng 1, 2024, 10:00

    https://luyencode.net/src/441116


  • 16
    tri_88  đã bình luận lúc 8, Tháng 1, 2024, 8:26

    Đầu tiên nhập vào một số n.

    Khi nào n > 0.

    Thì nhập vào 1 số a.

    Tiếp theo dùng hàm lower_bound() để tìm m là vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng với a

    Sau khi dùng hàm lower_bound() xong các bạn phải cộng thêm 1 vì vị trí m trong multiset thực tế là m+1.

    Rồi kiểm tra xem nều m != multiset.end() thì xoá m đi.

    (Nếu như m != multiset.end() thì xoá đi để tìm 1 vị trí khác thoả mãn)

    Thì kích thước của multiset sẽ là kết quả của bài.

    Code mẫu (C++) tại Đây


  • 0
    ngkhacbaolam2809  đã bình luận lúc 7, Tháng 1, 2024, 8:54 
    #include <bits/stdc++.h>
using namespace std;
long long n,a;
vector&lt;long long>v;

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
    cin >> a;
    auto it=lower_bound(v.begin(), v.end(), a);
    if(it==v.end()) v.push_back(a);
    else
        {
        *it=a;
        }
    }
    cout << v.size();
}

    Code Juan nha mn


  • 1
    LiuChi_3007  đã bình luận lúc 3, Tháng 1, 2024, 9:08

    Hỗ trợ mọi người nhaa!!!

    include <bits/stdc++.h>

    using namespace std;

    int main(){ ios::syncwithstdio(false); cin.tie(nullptr); int n; cin >> n ; int a[n]; for(int i=0;i<n;i++){ cin >> a[i]; } vector<int> v(n,1); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(a[i]>a[j]){ v[i] = max(v[i],v[j]+1); } } } cout << *max_element(v.begin(),v.end()); }


  • -3
    Na_yn  đã bình luận lúc 29, Tháng 12, 2023, 3:39

    Bài này dùng quy hoạch động nhá
    code:

    include <bits/stdc++.h>

    define int long long

    using namespace std;
    long long n,a;
    vector<int>v;
    int32t main()
    {
    cin >> n;
    for(int i=1; i<=n; i++)
    {
    cin >> a;
    auto it=lower    bound(v.begin(),v.end(),a);
    if(it==v.end()) v.push_back(a);
    else
    {
    *it=a;
    }
    }
    cout << v.size();
    }

    -Na.yn-


  • 0
    minyzin  đã bình luận lúc 13, Tháng 12, 2023, 13:51

    test 6 la jz mng;-;??


  • -3
    piecesmeow369  đã bình luận lúc 18, Tháng 7, 2023, 12:11

    include <iostream>

    using namespace std; int main(){ int n; long long a[1000]; long long b[1000]; cin >> n; for(int i = 1;i<=n;i++){ cin >>a[i]; }

    for(int i = 1;i<=n;i++){
    int count = 1;
    long long  max = a[i];
    for(int j = i;j<=n;j++){
        if(a[j] > max){
            max = a[j];
            count +=1;
        }
    }
    b[i] = count;
}
int max = b[1];
for(int i = 1;i<=n;i++){
    if(b[i] > max){
        max = b[i];
    }
}
cout << max;

return 0;}

    Ủa em chạy thử 1 vài case ngoài mà k biết lỗi ở đâu luôn á:') Mn giúp em với ạ


    • 1
      kimbang  đã bình luận lúc 27, Tháng 7, 2023, 3:29

      ví dụ 5 1 7 3 4 8 thì chuỗi con dài nhất phải là 4(1,3,4,8), mà code của bạn ra 3(1,7,8)