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

Tác giả:

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

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

2

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

Đã update test (credit: A519LeVanDuc)

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

1 phản hồi