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

Nguồn: vn.spoj

Bình luận

`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

Thuật \(O(n log_2 n)\) ở đây

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;
}

0
lagiahuy 6:06 p.m. 8 Tháng 10, 2021 ← chỉnh sửa 2 →
KHIẾP

OOO A OOO O O A A O O OOO AAAAA OOO

6 bình luận nữa