let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

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

solution.md

Đây là một bài quy hoạch động kinh điển. Gọi \(F(i)\) là dãy con tăng dài nhất kết thúc ở \(A(i)\), ta có công thức tính:

\[F(1) = 1\\ F(i) = max\{F(j)\} + 1\]

Với \(j\) thỏa \(1 \leq j \leq i-1\) và \(A(j) < A(i)\).

Kết quả bài toán là \(max\{F\}\). Bài này N có giới hạn nhỏ nên có thể dùng 2 vòng for để tính. Độ phức tạp: \(O(N^2)\)

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    vector<int> a(n);
    for (int &x: a) cin >> x;

    vector<int> f(n);
    int result = 1;
    for (int i=0; i<n; i++) {
        f[i] = 0;
        for (int j=i-1; j>=0; j--) if (a[i] > a[j]) {
            f[i] = max(f[i], f[j]);
        }
        f[i] += 1;
        result = max(result, f[i]);
    }

    cout << result;
    return 0;
}
Comments