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
    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++

      • 6 bình luận nữa