🎯 Mục tiêu bài học

• Hiểu khái niệm dãy con tăng dài nhất.
• Biết cách sử dụng DP để giải bài toán LIS.

📘 Mô tả bài toán

Cho dãy a₁, a₂, …, aₙ. Tìm độ dài lớn nhất của dãy con tăng dần.

📐 Công thức DP

dp[i] = 1 + max(dp[j]) với mọi j < i và a[j] < a[i]

💻 Thực hành

Python

n=int(input())
a=list(map(int,input().split()))
dp=[1]*n
for i in range(1,n):
    for j in range(i):
        if a[i]>a[j]:
            dp[i]=max(dp[i],dp[j]+1)
print(max(dp))

C++

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    vector<int> dp(n,1);
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
            if(a[i]>a[j])
                dp[i]=max(dp[i],dp[j]+1);
    cout<<*max_element(dp.begin(),dp.end());
}

🧩 Bài tập luyện tập

1. Tính độ dài LIS cho mảng bất kỳ.
2. In ra toàn bộ dãy con tăng dài nhất.
3. Tối ưu thuật toán LIS bằng tìm kiếm nhị phân để đạt O(n log n).

# Python (O(n log n))
import bisect
n=int(input())
a=list(map(int,input().split()))
lis=[]
for x in a:
    i=bisect.bisect_left(lis,x)
    if i==len(lis): lis.append(x)
    else: lis[i]=x
print(len(lis))