Dãy con tăng dài nhất: từ DP O(n²) tới tails O(n log n)

Dãy con khác đoạn con liên tiếp

Cho mảng [3,1,2,2,5,4]. Ta có thể lấy các vị trí mang 1,2,4 để được một dãy tăng dài 3, bỏ qua các vị trí không cần. Dãy con yêu cầu giữ thứ tự xuất hiện: không được sắp xếp lại mảng rồi gọi cả mảng đã sắp là đáp án.

Nếu yêu cầu liên tiếp, các phần tử được chọn phải nằm sát nhau và bài toán khác. Nếu yêu cầu không giảm, hai giá trị bằng nhau có thể đứng tiếp; ở đây đang học tăng nghiêm ngặt nên không được lấy cả hai số 2 nối nhau trong dãy tăng.

Trước khi nghĩ tới tối ưu, hãy viết rõ ba điều: có giữ thứ tự vị trí không, có bắt buộc liên tiếp không, có chấp nhận giá trị bằng nhau không. Cả công thức DP lẫn vị trí tìm kiếm nhị phân đều phụ thuộc các câu trả lời này.

DP O(n²): kết thúc ở đúng vị trí i

Đặt dp[i] là độ dài dãy tăng dài nhất kết thúc bằng a[i]. Mỗi phần tử đứng riêng tạo dãy dài 1, nên khởi tạo dp[i]=1. Để nối một phần tử trước đó, cần j<i và a[j]<a[i]; ứng viên là dp[j]+1. Lấy lớn nhất qua mọi j hợp lệ.

Đáp án là max trên mọi dp[i], không chỉ dp[n−1], vì dãy tốt nhất không nhất thiết kết thúc ở phần tử cuối. Ví dụ [1,2,3,0] có LIS dài 3 nhưng dãy kết thúc ở số 0 chỉ dài 1.

Hai vòng chỉ số cho O(n²) thời gian và O(n) bộ nhớ. Đây là cách dễ kiểm, dễ bổ sung parent để truy vết và rất hữu ích làm đối chứng cho bản nhanh trên dữ liệu nhỏ.

Vì sao chỉ cần nhớ đuôi nhỏ nhất?

Giả sử đã có hai dãy tăng cùng độ dài 3, một dãy kết thúc bằng 8, một dãy kết thúc bằng 5. Khi xét các phần tử tương lai, mọi giá trị nối được sau 8 cũng nối được sau 5; ngoài ra 6 hoặc 7 nối được sau 5 nhưng không sau 8. Vì thế đuôi 5 ít nhất không kém thuận lợi để kéo dài.

Ta không cần giữ mọi dãy cùng độ dài nếu chỉ hỏi độ dài tối ưu. Giữ đuôi nhỏ nhất cho từng độ dài là đủ để biết những khả năng nối tiếp. Khi có phần tử mới x, tìm độ dài thích hợp mà x có thể làm đuôi nhỏ hơn hoặc mở thêm một độ dài mới.

Các giá trị tails tăng nghiêm ngặt: đuôi tối ưu của một dãy dài hơn phải lớn hơn một giá trị đuôi phù hợp của độ dài ngắn hơn. Tính có thứ tự này cho phép tìm vị trí bằng nhị phân, thay vì quét mọi trạng thái cũ như bản O(n²).

lower_bound đặt x ở đâu?

Tìm vị trí đầu tiên có tails[pos]>=x. Nếu không có, x lớn hơn mọi đuôi và kéo dài dãy thêm một phần tử. Nếu có, thay tails[pos] bằng x, giữ nguyên độ dài nhưng cải thiện khả năng nối tiếp cho độ dài pos+1.

Với tails=[1,2,5] và x=4, vị trí đầu tiên >=4 là ô chứa 5. Thay thành [1,2,4]. Không khẳng định đã tìm được dãy dài hơn ngay lúc này; ta chỉ có đuôi thuận lợi hơn cho một dãy dài 3.

Với x=2 và tails=[1,2], vị trí đầu tiên >=2 là chính ô cuối, nên độ dài không tăng. Nếu dùng vị trí đầu tiên >x, phần tử bằng nhau sẽ có thể nối dài; đó là bản không giảm, không phải LIS tăng nghiêm ngặt đang xét.

Chạy tay tails trên cả mảng

Bắt đầu rỗng. Đọc 3 thì thêm thành [3]. Đọc 1 thì thay 3 vì đuôi 1 thuận lợi hơn. Đọc 2 thì nối sau 1 để thành [1,2]. Đọc số 2 tiếp theo chỉ thay ô 2 bằng chính 2, nên vẫn dài 2. Đọc 5 kéo dài lên 3; đọc 4 cải thiện đuôi cuối từ 5 thành 4.

Mỗi bước xử lý một phần tử, tìm vị trí O(log n), còn thao tác thay ô hoặc append là chi phí nhỏ trong mô hình mảng động phù hợp. Tổng bản fast là O(n log n), bộ nhớ O(n). Không dùng bisect.insort để chèn và dịch mảng ở giữa; ở đây ta thay đúng một ô, không giữ lại cả giá trị cũ lẫn mới.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int quadratic(const vector<int>& a){
    vector<int> d(a.size(),1);int answer=0;
    for(int i=0;i<(int)a.size();++i){
        for(int j=0;j<i;++j)if(a[j]<a[i])d[i]=max(d[i],d[j]+1);
        answer=max(answer,d[i]);
    }
    return answer;
}
int fast(const vector<int>& a){
    vector<int> tails;
    for(int x:a){
        auto p=lower_bound(tails.begin(),tails.end(),x);
        if(p==tails.end())tails.push_back(x);
        else *p=x;
    }
    return tails.size();
}
int main(){
    int n;vector<int> a={3,1,2,2,5,4};
    if(cin>>n){a.resize(n);for(int& x:a)cin>>x;}
    cout<<quadratic(a)<<' '<<fast(a)<<'\n';
}

from bisect import bisect_left
import sys

def quadratic(a):
    d=[1]*len(a)
    for i,x in enumerate(a):
        for j in range(i):
            if a[j]<x:
                d[i]=max(d[i],d[j]+1)
    return max(d,default=0)

def fast(a):
    tails=[]
    for x in a:
        i=bisect_left(tails,x)
        if i==len(tails):
            tails.append(x)
        else:
            tails[i]=x
    return len(tails)

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    values=a[1:1+a[0]] if a else [3,1,2,2,5,4]
    print(quadratic(values),fast(values))

Không nhập dữ liệu sẽ in 3 3, lần lượt từ quadratic và fast. Input riêng là n không âm rồi n số nguyên; giá trị cần vừa kiểu int C++. Mảng rỗng trả 0. Hai hàm không sửa mảng gốc.

Chương trình minh họa gọi cả hai hàm để đối chiếu, nên toàn chương trình vẫn mang chi phí O(n²) do bản quadratic. Khi giải đề n tới 100.000, chỉ gọi hàm fast phù hợp và đổi phần xuất theo đề. Đừng chạy cả bản chậm trong bài n lớn rồi kết luận thuật toán O(n log n) không đủ nhanh.

Trong Python, bisect_left tìm vị trí trong list tails; C++ lower_bound trả iterator. Cả hai đọc dãy đuôi đã có thứ tự, không thực hiện tìm kiếm nhị phân trực tiếp trên mảng input chưa được sắp xếp.

tails không phải luôn là một lời giải cụ thể

Xét [2,3,1]. Sau hai phần tử đầu, tails=[2,3]. Đọc 1 thì thay ô đầu, được [1,3]. Dãy này không phải dãy con theo đúng thứ tự input vì 1 xuất hiện sau 3. Nhưng độ dài 2 vẫn đúng, được chứng minh bởi dãy [2,3] đã tồn tại.

Các ô tails có thể đại diện cho những dãy khác nhau ở những thời điểm khác nhau; chúng không có nghĩa tất cả cùng thuộc một chuỗi vị trí thống nhất. Nếu cần in một LIS, lưu chỉ số phần tử đang làm đuôi cho mỗi độ dài và predecessor của từng phần tử khi xử lý. Sau cùng truy ngược từ chỉ số đuôi của độ dài lớn nhất.

Tương tự, độ dài không cho biết có bao nhiêu LIS. Bài đếm số dãy tối ưu cần thêm số cách, xử lý giá trị bằng nhau và quan hệ thứ tự cẩn thận, có thể dùng DP hoặc cấu trúc truy vấn. Không thể suy số lượng chỉ từ số lần append vào tails.

Dấu hiệu mở rộng cần suy nghĩ lại

Nếu đề hỏi tổng giá trị lớn nhất của một dãy tăng, chỉ giữ đuôi nhỏ nhất theo độ dài có thể làm mất một dãy tổng lớn. Nếu mỗi bước tăng bị giới hạn bởi K, điều kiện nối còn có cận trên. Nếu có hai tọa độ như phong bì, thứ tự sắp xếp và cách xử lý tọa độ bằng nhau quyết định có đếm nhầm hay không.

LIS thường là mảnh ghép cho nhiều bài, nhưng một dòng lower_bound không thay được phần mô hình hóa. Hãy xác định đối tượng đang so, quan hệ tăng và mục tiêu tối ưu trước khi dùng khung tails.

Kiểm với mọi tập con trên mảng nhỏ

Để tự kiểm tra trên mảng nhỏ (n ≤ 12), bạn có thể duyệt mọi tập con vị trí bằng bitmask, kiểm tra điều kiện tăng nghiêm ngặt rồi lấy độ dài lớn nhất để so sánh với hàm O(n²) và O(n log n) trên các ca mảng rỗng, một phần tử, toàn số bằng nhau, dãy giảm dần và dãy có số âm.

Các ca tự thử nên gồm [2,2,2] cho 1 ở bản tăng nghiêm ngặt nhưng 3 ở bản không giảm; [1,2,3,0] cho 3 dù dp cuối chỉ 1; [2,3,1] cho độ dài 2 nhưng tails cuối không phải lời giải cụ thể. Ba ca này kiểm ba hiểu nhầm khác nhau, không chỉ kiểm đầu ra mẫu một lần.

Luyện ngay trên Big-O Coding

Bắt đầu bằng bản DP để hiểu trạng thái kết thúc ở i. Với bài n tới 100.000, chuyển sang hàm fast và giữ các test số trùng để kiểm dấu so sánh. Bài phỏng vấn giúp luyện lại cùng ý tưởng qua định dạng hàm, nơi không cần tự đọc stdin như chương trình minh họa.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Longest increasing subsequence
• Python: bisect
• C++ reference: lower_bound