Dãy Số 3 (SEQ3)

Nguồn: NTUCoder Độ khó: Dễ Quy hoạch động Kadane Vét cạn

Đề bài

SEQ3 – Dãy số 3
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 512 megabyte

Yêu cầu: Tìm giá trị lớn nhất của biểu thức $a_i + a_{i+1} + \ldots + a_j$ $(1 \le i \lt j \le n)$.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên $n$ $(0 \lt n \le 10^6)$.
• Dòng thứ 2 là các số nguyên $a_1, a_2, \ldots, a_n$.

Kết quả: Một dòng duy nhất ghi giá trị lớn nhất của biểu thức.

Ví dụ – input

7
8 -10 6 -5 9 1 -3

Ví dụ – output

11

Lời mở đầu

Đề bài mô tả hơi "toán", nếu bạn nào chưa hiểu rõ thì mình tóm gọn lại: hãy tìm dãy con liên tiếp có tổng lớn nhất và in ra tổng đó. Ngắn gọn đơn giản vậy thôi ^^. Đây là bài toán kinh điển mở đầu cho quy hoạch động, và cũng là "anh em" với bài Dãy Số 4 (SEQ4) cùng series (bài đó tìm đoạn liên tiếp dài nhất có tổng bằng $k$).

Mình giải thích ví dụ mẫu: dãy 8 -10 6 -5 9 1 -3. Đoạn $6 + (-5) + 9 + 1 = 11$ (từ $i = 3$ đến $j = 6$) là lớn nhất. Các bạn có thể thắc mắc: sao không lấy $8$ hoặc $9$? Vì $8 \lt 11$ và $9 \lt 11$; cũng không thể "nhảy cóc" lấy $8 + 6 + 9$ vì các số đó không liền nhau.

Để ý điều kiện i < j: đoạn phải có ít nhất 2 phần tử

Đề ghi $1 \le i \lt j \le n$, tức là đoạn được chọn phải gồm ít nhất 2 phần tử liên tiếp. Với test của đề thì không khác gì (đáp án 11 đã gồm 4 phần tử), nhưng có những trường hợp khác hẳn:

• -5 -2 -7: nếu cho chọn 1 phần tử thì đáp án là $-2$, nhưng đúng đề thì phải chọn $\ge 2$ phần tử ⇒ $-5 + (-2) = \mathbf{-7}$.
• 5 -1: chọn 1 phần tử thì là $5$, đúng đề ⇒ $5 + (-1) = \mathbf{4}$.

Lời giải gốc mình đăng trên Facebook làm theo kiểu "đoạn bất kỳ, kể cả 1 phần tử". Trong bài này mình giữ nguyên ý tưởng nhưng chỉnh code một chút cho khớp điều kiện $i \lt j$ (mình sẽ chỉ rõ chỗ chỉnh ở từng cách). Riêng $n = 1$ thì không tồn tại cặp $i \lt j$, đề không nói in gì; code trong bài in luôn $a_1$.

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 1Vét cạn mọi đoạn · O(N²) · TLECách 2Quy hoạch động với mảng f · O(N)Cách 3Đọc tới đâu xử lý tới đó · O(N), bộ nhớ O(1)

Cách 1Vét cạn mọi dãy con liên tiếp – O(N²)

Cách đơn giản dễ nhận ra nhất: xét tất cả các dãy con liên tiếp, với từng dãy tính tổng rồi so sánh để tìm tổng lớn nhất. Với ví dụ của đề:

Bắt đầu từ 8: 8, -10 ⇒ -2 · 8 -10 6 ⇒ 4 · 8 -10 6 -5 ⇒ -1 · … 9 · 8 -10 6 -5 9 1 -3 ⇒ 6
Bắt đầu từ -10: -10 6 ⇒ -4 · -10 6 -5 ⇒ -9 · … ⇒ 1 · ⇒ -2
Bắt đầu từ 6: 6 -5 ⇒ 1 · 6 -5 9 ⇒ 10 · 6 -5 9 1 ⇒ 11 · 6 -5 9 1 -3 ⇒ 8
Bắt đầu từ -5: -5 9 ⇒ 4 · -5 9 1 ⇒ 5 · -5 9 1 -3 ⇒ 2
Bắt đầu từ 9: 9 1 ⇒ 10 · 9 1 -3 ⇒ 7
Bắt đầu từ 1: 1 -3 ⇒ -2
⇒ Tổng lớn nhất là 11 với dãy con 6 -5 9 1.

Cài đặt: xét từng vị trí $i$ làm điểm bắt đầu, rồi với mỗi $i$ duyệt $j$ từ $i + 1$ tới cuối, cộng dồn vào sum và liên tục cập nhật Max. Để đúng điều kiện $i \lt j$, mình khởi tạo sum = a[i] rồi mới cho $j$ chạy từ $i + 1$ (code gốc cho $j$ chạy từ $i$ nên tính cả đoạn 1 phần tử).

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    if(n == 1){
        cout << a[0];
        return 0;
    }
    long long Max = a[0] + a[1];
    for(int i = 0; i < n; ++i){
        long long sum = a[i];
        for(int j = i + 1; j < n; ++j){
            sum += a[j];
            Max = max(Max, sum);
        }
    }
    cout << Max;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1 + n]]
    if n == 1:
        print(a[0])
        return
    Max = a[0] + a[1]
    for i in range(n):
        s = a[i]
        for j in range(i + 1, n):
            s += a[j]
            Max = max(Max, s)
    print(Max)

main()

Giải thích một số chỗ trong code ở trên:

1. 2 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất khi code C++. Input lên tới 1 triệu số nên rất nên thêm vào (các bạn gõ mấy từ này lên Google là ra nhiều bài giải thích nhé).
2. Đề không cho giới hạn giá trị các phần tử nên để chắc ăn mình dùng long long (8 byte, lưu được tới hơn 9 tỷ tỷ), tránh tràn số như khi dùng int (chỉ hơn 2 tỷ).
3. Mảng tới 1 triệu phần tử thì dùng vector (mảng động). Kinh nghiệm: mảng tĩnh khai báo trong hàm chỉ nên tới khoảng $3 \cdot 10^5$ phần tử, quá thì dễ tràn bộ nhớ stack.
4. Max khởi tạo là a[0] + a[1] vì đằng nào đoạn gồm 2 phần tử đầu cũng là một đoạn hợp lệ. (Code gốc khởi tạo a[0], đúng cho bài "đoạn bất kỳ".)
5. Max = max(Max, sum); là cách viết gọn của if(sum > Max) Max = sum;.

C++▶ Chạy tay từng dòng codeCách 1: xét mọi đoạn [i, j] với i < j, cộng dồn sum, cập nhật Max, O(N²).

Dữ liệu vào (stdin) – sửa thoải mái7 8 -10 6 -5 9 1 -3

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 vector<long long> a(n);

10 for(int i = 0; i < n; ++i){

11 cin >> a[i];

12 }

13 if(n == 1){

14 cout << a[0];

15 return 0;

16 }

17 long long Max = a[0] + a[1];

18 for(int i = 0; i < n; ++i){

19 long long sum = a[i];

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

21 sum += a[j];

22 Max = max(Max, sum);

23 }

24 }

25 cout << Max;

26 return 0;

27}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(N)$ cho mảng $a$.
• Thời gian: $O(N)$ đọc mảng + $O(N^2)$ xử lý (hai vòng lặp lồng nhau, khoảng $\dfrac{N^2}{2}$ lần lặp) ⇒ $O(N^2)$ (phép ^ ở đây là lũy thừa chứ không phải xor nha các bạn).

Không gian$O(N)$

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

Chắc chắn TLE

$N = 10^6$ thì $N^2 = 10^{12}$, gấp $10^4$ lần ngưỡng khoảng $10^8$ phép tính/giây ⇒ cỡ 10.000 giây, gần 3 tiếng mới ra kết quả :)). Thực ra vừa nghĩ ra ý tưởng là nhẩm độ phức tạp đã biết không ổn. Nhưng mình vẫn khuyên: chưa nghĩ ra cách tối ưu thì cứ cài vét cạn, nó rất dễ cài và luôn đúng, dùng làm công cụ kiểm tra cho cách tối ưu về sau.

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

Cách giải trọn vẹn nhất chỉ cần $O(N)$, dùng phương pháp Quy hoạch động (Dynamic Programming), và bài này thuộc dạng QHĐ cơ bản. Mình sẽ tiếp cận theo kiểu tư duy thông thường để bạn nào chưa biết QHĐ cũng lờ mờ hiểu được.

Giả sử dãy lần lượt có thêm các phần tử A, B, C, D. Mỗi lần thêm một phần tử mới, ta chỉ ghi ra những dãy con liên tiếp mới xuất hiện (dấu | ngăn phần cũ với phần tử mới):

Thêm AA

Thêm BB
A | B

Thêm CC
B | C
A B | C

Thêm DD
C | D
B C | D
A B C | D

Các bạn thấy quy luật chưa? Các dãy con mới khi thêm D chính là: D đứng một mình, hoặc các dãy con mới của lần trước (C, B C, A B C) nối thêm D ở cuối. Đằng nào cũng cộng thêm D, vậy muốn tổng lớn nhất thì chỉ cần lấy dãy có tổng lớn nhất trong số các dãy mới của lần trước rồi nối D vào (hoặc D đứng một mình nếu như thế tốt hơn).

4 bước quy hoạch động

1. Bài toán con: $f[i]$ = tổng lớn nhất của dãy con liên tiếp kết thúc tại $a_i$.
2. Cơ sở: $f[0] = 0$ (chưa có phần tử nào).
3. Công thức truy hồi: $f[i] = \max(a_i,\ a_i + f[i-1])$.
4. Đáp án: với bài "đoạn bất kỳ" thì là $\max f[i]$. Với đúng đề này ($i \lt j$, ít nhất 2 phần tử): đoạn dài $\ge 2$ kết thúc tại $a_i$ chính là "đoạn tốt nhất kết thúc tại $a_{i-1}$" nối thêm $a_i$, nên đáp án là $\max\limits_{2 \le i \le n} \big(f[i-1] + a_i\big)$.

Để ý $f[1] = \max(a_1, a_1 + 0) = a_1$, đúng nghĩa đoạn duy nhất kết thúc tại $a_1$. Trong code, biến Max ở vòng lặp thứ 2 luôn là $f[i-1]$ (giá trị tốt nhất kết thúc ngay trước $a_i$), cập nhật đồng thời với f[i].

Minh hoạ: tính f[i] từ trái sang phải

Em nhập dãy rồi bấm Tiếp: mỗi bước quyết định "nối tiếp đoạn cũ" hay "bắt đầu lại từ $a_i$", và cập nhật đáp án $f[i-1] + a_i$:

Dãy a

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<long long> a(n + 1), f(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    if(n == 1){
        cout << a[1];
        return 0;
    }
    f[0] = 0;
    long long Max = f[0];
    for(int i = 1; i <= n; ++i){
        f[i] = Max = max(a[i], a[i] + Max);
    }
    Max = f[1] + a[2];
    for(int i = 2; i <= n; ++i){
        Max = max(Max, f[i - 1] + a[i]);
    }
    cout << Max;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [0] + [int(x) for x in data[1:1 + n]]
    if n == 1:
        print(a[1])
        return
    f = [0] * (n + 1)
    Max = f[0]
    for i in range(1, n + 1):
        Max = max(a[i], a[i] + Max)
        f[i] = Max
    Max = f[1] + a[2]
    for i in range(2, n + 1):
        Max = max(Max, f[i - 1] + a[i])
    print(Max)

main()

Giải thích nhanh: vòng lặp thứ 2 tính các $f[i]$, trong đó Max là giá trị tốt nhất của các đoạn kết thúc ngay trước $a_i$. Vòng lặp thứ 3 tìm đáp án: lớn nhất của f[i - 1] + a[i] với $i \ge 2$. (Code gốc của mình ở vòng 3 lấy $\max f[i]$, khởi tạo từ $f[0] = 0$, nên với dãy toàn số âm sẽ in 0, tức là "đoạn rỗng", không đúng với đề.)

C++▶ Chạy tay từng dòng codeCách 2: f[i] = max(a[i], a[i] + f[i-1]); đáp án = max f[i-1] + a[i] với i ≥ 2.

Dữ liệu vào (stdin) – sửa thoải mái7 8 -10 6 -5 9 1 -3

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 vector<long long> a(n + 1), f(n + 1);

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

11 cin >> a[i];

12 }

13 if(n == 1){

14 cout << a[1];

15 return 0;

16 }

17 f[0] = 0;

18 long long Max = f[0];

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

20 f[i] = Max = max(a[i], a[i] + Max);

21 }

22 Max = f[1] + a[2];

23 for(int i = 2; i <= n; ++i){

24 Max = max(Max, f[i - 1] + a[i]);

25 }

26 cout << Max;

27 return 0;

28}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(2N)$ cho 2 mảng $a$, $f$; bỏ hằng số ⇒ $O(N)$.
• Thời gian: 3 vòng lặp, mỗi vòng $N$ lần ⇒ $O(3N)$ ⇒ $O(N)$. Với $N = 10^6$ thì chỉ cỡ vài triệu phép tính, thấp hơn ngưỡng $10^8$ cả trăm lần ⇒ không sợ TLE. Đây cũng là độ phức tạp tốt nhất có thể, vì riêng việc đọc $N$ số đã tốn $O(N)$ rồi.

Không gian$O(N)$

Thời gian$O(N)$

Cách 3Đọc tới đâu xử lý tới đó – O(N), bộ nhớ O(1)

Code ở cách 2 mình cố tình tách ra từng bước cho dễ hình dung: đọc input, tính $f[i]$, tìm đáp án; 3 vòng lặp và thêm mảng $f$. Thực ra:

• Đọc lần lượt từng giá trị vào cũng chính là lần lượt xét từng $a_i$, tội gì đọc hết rồi mới xét lại? Ta xử lý ngay lúc đọc, chỉ cần 1 vòng lặp.
• Công thức chỉ cần $f[i-1]$ và $a_i$, không bao giờ nhìn lại các giá trị cũ hơn, nên không cần mảng $a$ hay $f$; chỉ cần 1 biến x để đọc vào là đủ.

Hai biến là đủ

Max1 = $f[i-1]$: tổng lớn nhất của đoạn kết thúc ngay trước phần tử đang đọc. Max2 = đáp án. Với mỗi x đọc vào (từ phần tử thứ 2):
1) Max2 = max(Max2, Max1 + x): đoạn ≥ 2 phần tử kết thúc tại x;
2) Max1 = max(x, Max1 + x): cập nhật $f$ cho bước sau.
Thứ tự rất quan trọng: phải dùng Max1 cũ để cập nhật Max2 trước, rồi mới cập nhật Max1.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long Max1, Max2 = LLONG_MIN, n, x;
    cin >> n >> x;
    Max1 = x;
    if(n == 1){
        cout << x;
        return 0;
    }
    n--;
    while(n--){
        cin >> x;
        Max2 = max(Max2, Max1 + x);
        Max1 = max(x, Max1 + x);
    }
    cout << Max2;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    x = int(data[1])
    Max1 = x
    if n == 1:
        print(x)
        return
    Max2 = None
    for t in data[2:1 + n]:
        x = int(t)
        cand = Max1 + x
        if Max2 is None or cand > Max2:
            Max2 = cand
        Max1 = max(x, Max1 + x)
    print(Max2)

main()

So với code gốc của mình (Max1 = Max2 = 0, cập nhật Max1 trước rồi Max2 = max(Max2, Max1)), bản này đọc riêng phần tử đầu tiên vào Max1, khởi tạo Max2 = LLONG_MIN (giá trị nhỏ nhất của long long, để giá trị đầu tiên chắc chắn lớn hơn) và đảo thứ tự 2 lệnh cập nhật, nhờ vậy đáp án luôn là đoạn ít nhất 2 phần tử và dãy toàn số âm cũng ra đúng.

C++▶ Chạy tay từng dòng codeCách 3: không cần mảng, Max1 = f[i-1], Max2 = đáp án; đọc tới đâu cập nhật tới đó.

Dữ liệu vào (stdin) – sửa thoải mái7 8 -10 6 -5 9 1 -3

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 long long Max1, Max2 = LLONG_MIN, n, x;

8 cin >> n >> x;

9 Max1 = x;

10 if(n == 1){

11 cout << x;

12 return 0;

13 }

14 n--;

15 while(n--){

16 cin >> x;

17 Max2 = max(Max2, Max1 + x);

18 Max1 = max(x, Max1 + x);

19 }

20 cout << Max2;

21 return 0;

22}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ vài biến ⇒ $O(1)$, tốt hơn hẳn $O(N)$ của cách 2.
• Thời gian: đúng 1 vòng lặp $N$ lần ⇒ $O(N)$, cùng bậc với cách 2 nhưng chạy ít việc hơn (không phải $3N$).

Không gian$O(1)$

Thời gian$O(N)$

Đến đây các bạn thấy luyện tư duy giải thuật quan trọng chứ? Từ cách ban đầu cần mảng và $O(N^2)$, trường hợp xấu nhất gần 3 tiếng mới chạy xong, thì cách sau cùng không cần mảng, chớp mắt cái là xong, mà code còn ngắn gọn hơn cả cách ban đầu nữa 😎. Ý tưởng "mang theo giá trị tốt nhất kết thúc tại vị trí trước" này còn có tên là thuật toán Kadane, các bạn nhớ nhé.

Ghi chú của mình: code C++ và Python của cả 3 cách đều in đúng 11 với test của đề, và đã được so với code vét cạn (đúng điều kiện $i \lt j$) trên 500 bộ test ngẫu nhiên nhỏ ($1 \le n \le 12$, có dãy toàn số âm, giá trị tới $\pm 10^{12}$) – khớp hết. Với $n = 10^6$ (giá trị tới $\pm 10^9$): cách 3 (C++) chạy khoảng 0.7 giây tính cả đọc input, cách 2 khoảng 0.6 giây; bản Python của cách 3 mất hơn 2 giây nên chỉ để tham khảo. Cách 1 với $n = 2 \cdot 10^4$ đã mất khoảng 0.8 giây, đúng là không thể chạy nổi $n = 10^6$. So với lời giải gốc trên Facebook, code đã được chỉnh để đáp án luôn là đoạn gồm ít nhất 2 phần tử như đề yêu cầu ($i \lt j$).

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 😇