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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
corona
Dạng bài
Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một dãy số nguyên gồm N phần tử \(A[1], A[2], ... A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],... A[i_k]\) thỏa mãn
\(i_1 < i_2 < ... < i_k\) và \(A[i_1] < A[i_2] < .. < A[i_k]\).

Yêu cầu:

  • 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ử.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 ≤ N ≤ 1000\))
  • Dòng thứ 2 ghi N số nguyên \(A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 1000000)\).

Kết quả

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

Test 1

Input 
6
1 2 5 4 6 2
Output 
4

Nguồn: vn.spoj

Bình luận


  • 0
    Phamduchiep    8:51 p.m. 13 Tháng 11, 2024

    sử dụng quy hoạch động

    code đã AC

    include<bits/stdc++.h>

    using namespace std;
    int n,a[1000005],t;
    int main(){
    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())<<'\n';
    }


    • 1
      LHL23_DoVanDuc    11:03 p.m. 4 Tháng 9, 2024

      include<bits/stdc++.h>

      define N 100002

      using namespace std;
      int n,a[N],f[N],g[N],c[N],d[N];
      int main()
      {
      ios_base::sync_with_stdio(false);
      cin.tie(0);cout.tie(0);
      cin>>n;
      for(int i=1;i<=n;i++) cin>>a[i];
      c[0]=0;
      int m=0;
      for(int i=1;i<=n;i++)
      {
      int x=lower_bound(c,c+m+1,a[i])-c-1;
      f[i]=x+1;
      if(x==m)
      {
      m++;
      c[m]=a[i];
      }
      else c[x+1]=min(c[x+1],a[i]);
      }
      int dmax=0;
      for(int i=1;i<=n;i++)
      {
      dmax=max(dmax,f[i]);
      }
      cout<<dmax;
      return 0;
      }


      • 0
        P12B3_04    3:37 p.m. 30 Tháng 8, 2024

        code nè:

        include <bits/stdc++.h>

        using namespace std;

        typedef long long ll;
        typedef pair<int,int> ii;
        typedef unsigned long long ull;

        define X first

        define Y second

        define pb push_back

        define mp make_pair

        define ep emplace_back

        define EL printf("\n")

        define sz(A) (int) A.size()

        define FOR(i,l,r) for (int i=l;i<=r;i++)

        define FOD(i,r,l) for (int i=r;i>=l;i--)

        define fillchar(a,x) memset(a, x, sizeof (a))

        define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

        const int N = 1005;
        int n, a[N], F[N];

        int main() {
        // freopen("INP.TXT", "r", stdin);
        // freopen("OUT.TXT", "w", stdout);

        cin >> n;
FOR(i,1,n) scanf("%d", &a[i]);

a[++n] = 10001;
FOR(j,1,n) {
    F[j] = 1;
    FOR(i,1,j-1) if (a[i] < a[j]) F[j] = max(F[j], F[i]+1);
}

cout << F[n]-1;

return 0;

        }
        c++


        • 0
          nongducquan    10:02 p.m. 5 Tháng 6, 2024

          bài này là quy hoạch động cơ bản LIS các bạn có thể lên mạng xem


          • 2
            thieukhangduong    3:30 p.m. 6 Tháng 5, 2024 

            def longest_increasing_subsequence_length(arr):
    n = len(arr)
    lis = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return max(lis)
##################################################################
N = int(input())
A = list(map(int, input().split()))
print(longest_increasing_subsequence_length(A))

            python 3 nha


            • 1
              cuom1999    1:39 a.m. 15 Tháng 7, 2020

              Đã update test (credit: A519LeVanDuc)


              • 5
                SPyofgame    5:24 a.m. 14 Tháng 6, 2020

                Spoiler Alert

                Hint 1

                • Thử từng dãy con một

                Kiểm tra xem nếu nó là dãy con tăng dần

                Xuất dãy có độ dài dài max

                Hint 2

                • Gọi mảng \(f[]\) với \(f_i\) là giá trị độ dài tối đa tính tới \(i\) || init \(f_i = 1\)

                Ta duyệt \(\forall j < i\) tìm vị trí \(j\) thỏa \(a_j < a_i\)

                Ta liên tục chọn các vị trí \(j\) có \(f_j\) lớn nhất

                \(result = max(x \in f)\)

                Hint 3

                • Nếu các bạn muốn lấy mảng LIS

                Gọi mảng \(LIS[]\) là mảng cần tìm

                Duyệt ngược từ vị trí cuối về, nếu \(f_i = res\) thì thêm phần tử vào cuối mảng \(LIS\) rồi giảm res

                Đảo ngược lại mảng \(LIS[]\) sau quá trình trên ta thu được dãy con dài nhất

                Hint 4

                Sử dụng chặt nhị phân với mảng \(b[]\) có \(b_i\) là giá trị nhỏ nhất các dãy \(LIS\) độ dài \(i\)

                Reference AC code | \(O(n ^ 2)\) time | \(O(n)\) auxiliary space | LIS-problem, DP

                C++
                int lis(const vector<int> a)
{
    int n = a.size();
    vector<int> f(n, 1);

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[i] > a[j])
                maximize(f[i], f[j] + 1);

    int res = *max_element(f.begin(), f.end());
    return res;

    /// lay mang LIS
    vector<int> LIS;
    while (n--)
        if (f[n] == res)
            LIS.push_back(a[n]), res--;

    reverse(all(LIS));
    return LIS.size();
}

                Reference AC code | \(O(n ^ 2)\) time | \(O(n)\) auxiliary space | Online solving, LIS-problem, DP

                C++
                int main()
{
    int n = readInt();
    vector<int> a, f;

    int res = 1;
    for (int i = 0; i < n; ++i) {
        a.push_back(readInt());
        f.push_back(1);

        for (int j = 0; j < i; ++j)
            if (a[i] > a[j])
                maximize(f[i], f[j] + 1),
                maximize(res, f[i]);
    }

    cout << res;
    return 0;
}
                1 phản hồi