Dãy con tăng dài nhất (LIS)

Mức độ: Nâng cao

Từ dãy 3 1 4 1 5 9 2 6, xóa đi một số phần tử (giữ nguyên thứ tự các phần tử còn lại) để được dãy tăng ngặt dài nhất. Ví dụ 1 4 5 9 hoặc 3 4 5 6, dài 4. Đây là bài dãy con tăng dài nhất (LIS), bài mẫu quen thuộc nhất của quy hoạch động.

Quy hoạch động n²

Gọi dai[i] là độ dài dãy con tăng dài nhất kết thúc tại a_i. Dãy đó gồm a_i đứng cuối, trước nó là một dãy con tăng kết thúc tại a_j nào đó với j đứng trước i và a_j nhỏ hơn a_i (hoặc không có gì):

dai[i] = 1 + max(dai[j] với j nhỏ hơn i và a_j nhỏ hơn a_i) (max của tập rỗng coi là 0)

i	1	2	3	4	5	6	7	8
a_i	3	1	4	1	5	9	2	6
dai[i]	1	1	2	1	3	4	2	4

Đáp số là dai lớn nhất, 4. Mỗi i xét mọi j đứng trước, cả bài khoảng n² / 2 bước: n = 5000 là khoảng 10⁷, n = 10⁵ thì quá chậm.

Cách n log n: đuôi nhỏ nhất

Giữ mảng duoi: duoi[k] là số cuối nhỏ nhất của một dãy con tăng dài k + 1 trong các phần tử đã xét. Đuôi càng nhỏ càng dễ nối thêm, nên chỉ cần nhớ đuôi nhỏ nhất cho mỗi độ dài.

Mảng duoi luôn tăng ngặt (dãy dài hơn thì đuôi lớn hơn). Khi xét a_i:

tìm vị trí k đầu tiên có duoi[k] ≥ a_i bằng tìm kiếm nhị phân;
nếu không có (a_i lớn hơn mọi đuôi): nối a_i vào cuối, độ dài tăng 1;
nếu có: thay duoi[k] = a[i] (có dãy dài k + 1 với đuôi nhỏ hơn trước).

a_i	duoi sau khi xét
3	3
1	1
4	1 4
1	1 4
5	1 4 5
9	1 4 5 9
2	1 2 5 9
6	1 2 5 6

Độ dài mảng duoi cuối cùng là đáp số, 4. Lưu ý mảng duoi không phải là một dãy con tăng (1 2 5 6 không xuất hiện theo đúng thứ tự trong dãy), chỉ độ dài của nó là đúng.

Python
C++

import sys
from bisect import bisect_left
du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])
duoi = []
for x in map(int, du_lieu[1:1 + n]):
    k = bisect_left(duoi, x)          # vị trí đầu tiên có duoi[k] >= x
    if k == len(duoi):
        duoi.append(x)
    else:
        duoi[k] = x
print(len(duoi))

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> duoi;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        auto it = lower_bound(duoi.begin(), duoi.end(), x);   // duoi[k] >= x đầu tiên
        if (it == duoi.end()) duoi.push_back(x);
        else *it = x;
    }
    cout << duoi.size() << "\n";
    return 0;
}

Mỗi phần tử một lần tìm kiếm nhị phân, cả bài khoảng n × log₂n bước.

Các biến thể

Đề hỏi	Thay đổi
dãy con không giảm dài nhất	dùng `bisect_right` (C++ `upper_bound`) thay `bisect_left`
dãy con giảm dài nhất	đổi dấu mọi số rồi tìm dãy con tăng
ít nhất phải xóa mấy số để dãy tăng	n - (độ dài dãy con tăng dài nhất)
cặp (rộng, cao), xếp lồng nhau	sắp xếp theo rộng tăng dần, rộng bằng nhau thì cao giảm dần, rồi tìm dãy con tăng theo cao

Với cặp (rộng, cao), cao giảm dần khi rộng bằng nhau để hai hộp cùng rộng không bị chọn lồng vào nhau.

Luyện tập

Gồm 16 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Độ dài dãy con tăng

Bài 1. Độ dài dãy con tăng dài nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra độ dài dãy con tăng ngặt dài nhất.

Ví dụ:

Nhập	In ra
`8` `3 1 4 1 5 9 2 6`	`4`

Kiểm tra: nhập

12
10 -3 7 7 2 8 -1 9 4 5 6 1

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Dãy con không giảm dài nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra độ dài dãy con không giảm dài nhất (cho phép hai số liền nhau bằng nhau).

Ví dụ:

Nhập	In ra
`7` `2 2 1 3 3 2 4`	`5`

Kiểm tra: nhập

10
5 5 5 1 1 6 1 5 5 2

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Dãy con giảm dài nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra độ dài dãy con giảm ngặt dài nhất.

Ví dụ:

Nhập	In ra
`7` `5 8 3 7 2 6 1`	`4`

Kiểm tra: nhập

10
-1 4 4 3 9 0 -2 5 -3 -8

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Độ dài dãy con tăng kết thúc tại từng vị trí

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Với mỗi i, in ra độ dài dãy con tăng ngặt dài nhất kết thúc tại a_i.

Ví dụ:

Nhập	In ra
`8` `3 1 4 1 5 9 2 6`	`1 1 2 1 3 4 2 4`

Kiểm tra: nhập

10
4 2 6 3 5 1 7 7 0 8

Xem đáp số

1 1 2 2 3 1 4 4 1 5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Xóa ít nhất để dãy tăng

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số phần tử ít nhất cần xóa để các phần tử còn lại tạo thành dãy tăng ngặt.

Ví dụ:

Nhập	In ra
`6` `4 2 5 3 6 1`	`3`

Kiểm tra: nhập

10
1 9 2 8 3 7 4 6 5 5

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Biến đổi về dãy con tăng

Bài 6. Sửa ít nhất để dãy tăng ngặt

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Mỗi lần được đổi một phần tử thành số nguyên bất kỳ. In ra số lần đổi ít nhất để dãy tăng ngặt.

Ví dụ:

Nhập	In ra
`5` `1 2 2 3 4`	`2`

Kiểm tra: nhập

8
5 1 2 3 10 4 5 6

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Cầu không cắt nhau

Hai bờ sông song song. Có n cặp thành phố muốn nối cầu, cặp thứ i nối điểm a_i ở bờ trái với điểm b_i ở bờ phải (các a_i khác nhau, các b_i khác nhau). Hai cây cầu cắt nhau nếu a_i nhỏ hơn a_j nhưng b_i lớn hơn b_j. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có a, b (1 ≤ a, b ≤ 10⁹). In ra số cầu nhiều nhất xây được mà không có hai cầu nào cắt nhau.

Ví dụ:

Nhập	In ra
`5` `1 3` `2 1` `3 4` `4 2` `5 5`	`3`

Kiểm tra: nhập

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Xếp hộp lồng nhau

Có n hộp, hộp thứ i có đáy hình chữ nhật rộng w_i, dài h_i (không được xoay). Hộp A bỏ vừa vào hộp B nếu w_A nhỏ hơn w_B và h_A nhỏ hơn h_B. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có w, h (1 ≤ w, h ≤ 10⁹). In ra số hộp nhiều nhất lồng được vào nhau thành một chồng.

Ví dụ:

Nhập	In ra
`4` `5 4` `6 4` `6 7` `2 3`	`3`

Kiểm tra: nhập

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Ít cột nhất

Có n tấm thẻ đến lần lượt, tấm thứ i ghi số a_i. Mỗi tấm được đặt lên trên cùng một cột: tấm mới phải ghi số nhỏ hơn hoặc bằng tấm đang trên cùng cột đó, hoặc lập một cột mới. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số a_i (|a_i| ≤ 10⁹). In ra số cột ít nhất.

Ví dụ:

Nhập	In ra
`7` `5 2 6 1 3 4 2`	`3`

Kiểm tra: nhập

10
3 3 3 1 4 1 5 9 2 6

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Kết hợp hai chiều

Bài 10. Dãy con hình núi

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Dãy con hình núi là dãy con tăng ngặt rồi giảm ngặt (phần tăng hoặc phần giảm có thể chỉ gồm một số là đỉnh). In ra độ dài dãy con hình núi dài nhất.

Ví dụ:

Nhập	In ra
`8` `1 11 2 10 4 5 2 1`	`6`

Kiểm tra: nhập

10
3 1 4 1 5 9 2 6 5 3

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Dãy con tăng với bước nhảy không quá k

Dòng đầu có n, k (1 ≤ n ≤ 3000, 1 ≤ k ≤ 10⁹), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Tìm dãy con tăng ngặt dài nhất mà hai số liền nhau trong dãy con chênh nhau không quá k. In ra độ dài của nó.

Ví dụ:

Nhập	In ra
`7 2` `1 5 2 3 6 4 8`	`4`

Kiểm tra: nhập

10 3
10 1 4 2 7 5 8 11 9 12

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Dãy con chung tăng dài nhất

Dòng đầu có n, m (1 ≤ n, m ≤ 3000), dòng thứ hai có n số của dãy A, dòng thứ ba có m số của dãy B (|giá trị| ≤ 10⁹). In ra độ dài dãy dài nhất vừa là dãy con của A, vừa là dãy con của B, và tăng ngặt.

Ví dụ:

Nhập	In ra
`5 5` `2 3 1 6 5` `3 1 2 6 5`	`2`

Kiểm tra: nhập

8 7
1 4 2 5 3 6 7 2
4 1 5 2 6 3 7

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Truy vết, đếm, tổng

Bài 13. In ra dãy con tăng dài nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra độ dài dãy con tăng ngặt dài nhất trên dòng đầu, dòng thứ hai in ra các vị trí (đánh số từ 1) của một dãy như vậy. Nếu có nhiều dãy, in dãy có vị trí cuối cùng lớn nhất; nếu vẫn còn nhiều, chọn dãy có vị trí áp chót lớn nhất, và cứ thế đi ngược về đầu.

Ví dụ:

Nhập	In ra
`8` `3 1 4 1 5 9 2 6`	`4` `2 3 5 8`

Kiểm tra: nhập

10
2 7 1 8 2 8 1 8 2 8

Xem đáp số

3
7 9 10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Đếm số dãy con tăng dài nhất

Dòng đầu có n (1 ≤ n ≤ 3000), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số dãy con tăng ngặt có độ dài lớn nhất (hai dãy con khác nhau nếu tập vị trí khác nhau), chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
`6` `1 3 2 4 3 5`	`3`

Kiểm tra: nhập

10
2 2 2 2 2 2 2 2 2 2

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Dãy con tăng có tổng lớn nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹). In ra tổng lớn nhất của một dãy con tăng ngặt (không cần dài nhất).

Ví dụ:

Nhập	In ra
`6` `1 101 2 3 100 4`	`106`

Kiểm tra: nhập

10
5 3 8 1 9 2 10 4 7 6

Xem đáp số

32

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Dãy con lên xuống dài nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Dãy con lên xuống là dãy con mà các hiệu giữa hai số liền nhau đổi dấu luân phiên (dương, âm, dương… hoặc âm, dương, âm…; không có hiệu bằng 0). Dãy một số cũng là dãy lên xuống. In ra độ dài dãy con lên xuống dài nhất.

Ví dụ:

Nhập	In ra
`6` `1 7 4 9 2 5`	`6`

Kiểm tra: nhập

10
1 17 5 10 13 15 10 5 16 8

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English

Dãy con tăng dài nhất (LIS)

Quy hoạch động n2

Cách n log n: đuôi nhỏ nhất

Các biến thể

Luyện tập

Nhóm 1. Độ dài dãy con tăng

Bài 1. Độ dài dãy con tăng dài nhất

Bài 2. Dãy con không giảm dài nhất

Bài 3. Dãy con giảm dài nhất

Bài 4. Độ dài dãy con tăng kết thúc tại từng vị trí

Bài 5. Xóa ít nhất để dãy tăng

Nhóm 2. Biến đổi về dãy con tăng

Bài 6. Sửa ít nhất để dãy tăng ngặt

Bài 7. Cầu không cắt nhau

Bài 8. Xếp hộp lồng nhau

Bài 9. Ít cột nhất

Nhóm 3. Kết hợp hai chiều

Bài 10. Dãy con hình núi

Bài 11. Dãy con tăng với bước nhảy không quá k

Bài 12. Dãy con chung tăng dài nhất

Nhóm 4. Truy vết, đếm, tổng

Bài 13. In ra dãy con tăng dài nhất

Bài 14. Đếm số dãy con tăng dài nhất

Bài 15. Dãy con tăng có tổng lớn nhất

Bài 16. Dãy con lên xuống dài nhất

Quy hoạch động n²