Dãy Con Tăng Dài Nhất – Bản Dễ (DCTDN1)

Nguồn: LuyenCode Độ khó: Dễ Quy hoạch động Dãy con tăng dài nhất

Đề bài

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

Cho một dãy số nguyên gồm $N$ phần tử $a_1, a_2, \ldots, a_N$. Một dãy con đơn điệu tăng của dãy trên là dãy $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ sao cho: $i_1 \lt i_2 \lt \ldots \lt i_k$ và $a_{i_1} \lt a_{i_2} \lt \ldots \lt a_{i_k}$. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương $N$;
• Dòng thứ hai chứa $N$ số nguyên dương $a_1, a_2, \ldots, a_N$, mỗi số cách nhau bởi một dấu cách.

Giới hạn: $1 \le n \le 1000,\ -10^9 \le a_i \le 10^9$.

Dữ liệu ra: Ghi ra độ dài của dãy con đơn điệu tăng dài nhất.

Input #1

6
1 2 5 4 6 2

Output #1

4

Giải thích #1: Dãy con tăng dài nhất là dãy $1, 2, 4, 6$, độ dài dãy này là $4$.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Đây là bài "kinh điển" mà hầu như ai học quy hoạch động cũng phải gặp qua, nên các bạn nắm chắc bài này nha.

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Dãy là 1 2 5 4 6 2. "Dãy con" nghĩa là ta được bỏ bớt một số phần tử nhưng giữ nguyên thứ tự các phần tử còn lại (không cần liền nhau). "Tăng" ở đây là tăng ngặt: phần tử sau phải lớn hơn hẳn phần tử trước, bằng nhau là không được.

• Lấy $1, 2, 5, 6$ (bỏ số $4$ và số $2$ cuối) → tăng, dài $4$.
• Lấy $1, 2, 4, 6$ (bỏ số $5$ và số $2$ cuối) → tăng, dài $4$.
• Không thể lấy được $5$ số: muốn lấy cả $5$ và $4$ thì $5$ đứng trước $4$ mà $5 \gt 4$ → không tăng; còn số $2$ cuối cùng lại bằng số $2$ ở vị trí 2 nên cũng không ghép thêm được.

Vậy đáp án là 4. Đề chỉ hỏi độ dài, không bắt in ra dãy, nên có nhiều dãy cùng dài nhất cũng không sao.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Quy hoạch động O(N²) · AC bản dễMở rộngBản trung bình & khó cần O(N log N)

Cách 1Quy hoạch động – O(N²)

Bài này áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nhé các bạn. Cho bạn nào đã có biết cơ bản qua về quy hoạch động rồi thì 4 bước giải một bài toán quy hoạch động như sau:

1Bài toán con: Gọi $F[i]$ là độ dài dãy con tăng dài nhất tính từ đầu mảng khi xét đến vị trí $i$ và lấy luôn phần tử $a[i]$ (tức dãy con tăng kết thúc tại $a[i]$).

2Bài toán cơ sở: $F[0] = 0$, bởi khi dãy chưa có phần tử nào cả thì độ dài dãy con dài nhất sẽ là $0$.

3Đáp án: là giá trị $F[i]$ lớn nhất trong tất cả các $F[i]$ với $0 \le i \le N$, ký hiệu $\max(F[i])$.

4Công thức truy hồi: Khi xét đến vị trí $i$, xét tất cả các vị trí đứng trước $j = 0 \to i - 1$; trong những vị trí $j$ thỏa $a[j] \lt a[i]$ thì tìm $\max$ của các $F[j]$, rồi $F[i] = \max + 1$.

Công thức truy hồi

$F[i] = 1 + \max\{\, F[j] \ \mid\ 0 \le j \lt i,\ a[j] \lt a[i] \,\}$ (với $F[0] = 0$ đóng vai trò "dãy rỗng").
Đáp án $= \max\limits_{1 \le i \le N} F[i]$.

Khá dễ hiểu vì sao lại như vậy đúng không các bạn? Ta chỉ có thể nhận phần tử $a[i]$ hiện tại vào dãy con tăng nếu phần tử cuối cùng của dãy con tăng đó nhỏ hơn $a[i]$, vì quy luật đề bài đưa ra là như vậy. Giả sử dãy con tăng có phần tử cuối cùng là $a[j]$ và thấy $a[j] \lt a[i]$, nghĩa là dãy con tăng kết thúc tại $a[j]$ đó có thể kết nạp thêm $a[i]$ vào cuối, như thế độ dài được cộng thêm 1: $F[i] = F[j] + 1$.

Và cứ $a[j]$ nào đứng trước mà thỏa $a[j] \lt a[i]$ thì đều có thể nối thêm $a[i]$ vào cuối. Để $F[i]$ lớn nhất thì ta tìm $F[j]$ lớn nhất trong tất cả các $j$ thỏa mãn rồi cộng thêm 1. Cuối cùng, đáp án là $F[i]$ lớn nhất trong tất cả các $F[i]$, bởi vì dãy con tăng dài nhất có thể kết thúc tại bất kỳ phần tử nào mà.

Thử với ví dụ của đề $a = [1, 2, 5, 4, 6, 2]$ cho dễ hình dung:

$i$	1	2	3	4	5	6
$a[i]$	1	2	5	4	6	2
các $j$ có $a[j] \lt a[i]$	không có	1	1, 2	1, 2	1, 2, 3, 4	1
$F[i]$	0+1 = 1	1+1 = 2	2+1 = 3	2+1 = 3	3+1 = 4	1+1 = 2

$\max F[i] = F[5] = 4$ → khớp đáp án. Để ý số $2$ ở cuối: số $2$ ở vị trí 2 không được tính vì $2 \lt 2$ là sai (tăng ngặt).

Các lưu ý nhỏ mà hay

1/ Nếu không có $a[j]$ nào đứng trước nhỏ hơn $a[i]$ thì $F[i] = 1$ (dãy con tăng chỉ gồm mình $a[i]$). Vì vậy giá trị Max ban đầu nên khởi tạo bằng $0$, để nếu không có gì cập nhật thì $F[i] = 0 + 1 = 1$. Trong code mình dùng biến idxMax (vị trí $j$ có $F[j]$ lớn nhất), ban đầu idxMax = 0; nếu không cập nhật thì $F[i] = F[0] + 1 = 1$ – chính là chỗ dùng bài toán cơ sở $F[0] = 0$ ở bước 2.

2/ Không cần tính xong hết các $F[i]$ rồi mới làm thêm một vòng lặp tìm max: cứ tính xong $F[i]$ nào thì so với res và cập nhật luôn.

3/ Thậm chí không cần nhập hết mảng rồi mới xử lý: đọc $a[i]$ xong là tính $F[i]$ được ngay, vì $F[i]$ chỉ cần các $a[j]$ đứng trước – những phần tử đã được nhập vào mảng rồi.

Minh hoạ tính mảng F

Em nhập dãy rồi bấm Tiếp để xem với mỗi $i$, ta duyệt các $j$ đứng trước như thế nào (ô xanh = $a[j] \lt a[i]$ dùng được, ô đỏ = không nối được). Bước cuối sẽ dò ngược lại để chỉ ra một dãy con tăng dài nhất.

Dãy a

Ví dụ nhanh:

Source code để các bạn tham khảo với những gì mình phân tích ở trên:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n + 1], f[n + 1], res = 0;
    f[0] = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        int idxMax = 0;
        for(int j = 1; j < i; ++j){
            if(a[j] < a[i] && f[j] > f[idxMax]){
                idxMax = j;
            }
        }
        f[i] = f[idxMax] + 1;
        res = max(res, f[i]);
    }
    cout << res;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [0] * (n + 1)
    f = [0] * (n + 1)
    res = 0
    f[0] = 0
    for i in range(1, n + 1):
        a[i] = int(data[i])
        idxMax = 0
        for j in range(1, i):
            if a[j] < a[i] and f[j] > f[idxMax]:
                idxMax = j
        f[i] = f[idxMax] + 1
        res = max(res, f[i])
    print(res)

main()

C++▶ Chạy tay từng dòng codeQHĐ O(N²): đọc a[i] xong tính luôn F[i] = F[idxMax] + 1, cập nhật res.

Dữ liệu vào (stdin) – sửa thoải mái6 1 2 5 4 6 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n;

8 cin >> n;

9 int a[n + 1], f[n + 1], res = 0;

10 f[0] = 0;

11 for(int i = 1; i <= n; ++i){

12 cin >> a[i];

13 int idxMax = 0;

14 for(int j = 1; j < i; ++j){

15 if(a[j] < a[i] && f[j] > f[idxMax]){

16 idxMax = j;

17 }

18 }

19 f[i] = f[idxMax] + 1;

20 res = max(res, f[i]);

21 }

22 cout << res;

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: Toàn bài ta dùng 2 mảng $a$, $f$, mỗi mảng $N + 1$ phần tử, làm tròn coi như $N$ ⇒ $O(2 \cdot N)$. Theo quy tắc nhân Big-O thì nhân với hằng số có thể bỏ qua, nên tổng quát là $O(N)$.
• Thời gian: 2 vòng lặp $i$, $j$ lồng nhau. Vòng $i$ chạy từ $1$ đến $N$, với mỗi $i$ thì vòng $j$ chạy từ $1$ đến $i - 1$. Tổng số lần lặp là $0 + 1 + 2 + \ldots + (N - 1) = \dfrac{N(N - 1)}{2} = 0.5 \cdot (N^2 - N)$. Bỏ hằng số $0.5$ (quy tắc nhân), rồi giữa $N^2$ và $-N$ ta lấy thành phần lớn nhất (quy tắc cộng) ⇒ $O(N^2)$ nha các bạn (dấu ^ ở đây là lũy thừa chứ không phải phép xor bit nhé).

Không gian$O(N)$

Thời gian$O(N^2)$

Với trường hợp xấu nhất $N = 1000$ thì $N^2 = 10^6$ (thực tế chỉ khoảng $5 \cdot 10^5$ lần lặp), quá ít so với ngưỡng cỡ $3 \cdot 10^7$ đến $10^8$ phép tính trong 1 giây, nên yên tâm không bị TLE.

Tăng ngặt: dùng dấu < chứ không phải <=

Đề yêu cầu $a_{i_1} \lt a_{i_2} \lt \ldots$ nên điều kiện phải là a[j] < a[i]. Nếu lỡ viết a[j] <= a[i] thì bạn đang tính dãy con không giảm, test như 7 7 7 7 sẽ ra 4 thay vì 1. Giá trị $|a_i| \le 10^9$ vẫn vừa kiểu int nên không lo tràn số.

Mở rộngBản trung bình và bản khó

Mình cũng nói luôn: cách làm $O(N^2)$ ở trên chưa phải tối ưu nhất cho bài toán dãy con tăng dài nhất. Ta có thể tối ưu xuống $O(N \log N)$. Tuy nhiên ở mức độ bài này ($N \le 1000$) thì $O(N^2)$ là đủ Accepted rồi.

Bài này chỉ là bản dễ, còn có bản trung bình (DCTDN2) và bản khó (DCTDN3) – lúc đó phải dùng thuật toán $O(N \log N)$ mới Accepted được. Các bạn thử sức làm 2 bài này trước nhé, hẹn các bạn trong một bài đăng gần nhất mình sẽ giải quyết cả 2 bài này cho các bạn tham khảo 😉.

Ghi chú của mình: code C++ và Python ở trên đã được chạy đúng với test của đề, và được so khớp với code vét cạn (thử mọi tập con) trên 400 bộ test ngẫu nhiên ($n \le 12$, có số âm, có số trùng nhau) – khớp hết. Với $n = 1000$ (dãy ngẫu nhiên và dãy tăng dần), bản C++ chạy dưới 0.1 giây, bản Python khoảng 0.5–0.65 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇