Dãy số 2 (SEQ2)

Nguồn: NTUCoder (THPT Chuyên) Độ khó: Trung bình Quy hoạch động Max 1, Max 2 Tư duy

Đề bài

SEQ2 – Dãy số 2

Yêu cầu: Tìm giá trị lớn nhất của biểu thức $a_i + a_j - a_k$ $(1 \le i \lt j \lt k \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.

Giới hạn: thời gian 1 giây, bộ nhớ 512 MB.

Ví dụ – input

7
8 2 4 -5 9 1 -3

Ví dụ – output

20

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 😇.

Mình nói luôn bài này là bài "Dãy số 2". Nếu bạn nào vẫn chưa làm được thì trước tiên hãy thử làm bài "Dãy số 1" (tìm hiệu lớn nhất $a_j - a_i$ với $i \lt j$). Bài 1 có thể xem là bài con của bài 2: làm được bài 1 thì sẽ có cơ sở để làm bài 2, vì dạng của nó cũng tương đồng, chỉ là làm rối lên một tí ^^. Hãy đảm bảo là bạn đã cố gắng hết sức mà vẫn không được, hoặc đã tự làm được rồi, thì mới xem tiếp bài giải dưới đây nhé.

Trước khi vào bài, các bạn nhớ giúp mình chuyện giới hạn thời gian: với các hệ thống chấm bài giới hạn 1 giây, toàn bài chỉ nên lặp cỡ $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất $10^8$ lần (lúc này hên xui). Ngưỡng này là cho C/C++; Python, Java, C# chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 100 ms thì chia 10, cứ thế mà tính.

Giải thích ví dụ cho bạn nào chưa hiểu đề: dãy là 8 2 4 -5 9 1 -3. Ta chọn 3 vị trí $i \lt j \lt k$, hai số ở trước được cộng, số đứng sau cùng bị trừ. Chọn $a_1 = 8$, $a_5 = 9$ và $a_7 = -3$ ta được $8 + 9 - (-3) = 20$, và không có bộ ba nào cho kết quả lớn hơn ⇒ đáp án $20$.

824-591-3

Xanh = hai số được cộng ($a_i$, $a_j$), đỏ = số bị trừ ($a_k$, phải đứng sau cả hai). $8 + 9 - (-3) = 20$.

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 bộ ba · O(N³)Cách 2Quy hoạch động, giữ Max1 Max2 · O(N)Cách 3Không cần mảng · bộ nhớ O(1)

Cách 1Vét cạn mọi bộ ba (i, j, k) – O(N³)

Cách làm cơ bản nhất, dễ nhìn ra nhất: xét hết tất cả các bộ ba $(i, j, k)$ thoả $i \lt j \lt k$, tính $a_i + a_j - a_k$ rồi liên tục so sánh để sau cùng tìm ra kết quả lớn nhất trong tất cả các bộ ba hợp lệ – đó chính là đáp án.

Source code để các bạn tham khảo tư tưởng xử lý ở trên:

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

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

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
if n < 3:
    print(0)
else:
    a = list(map(int, data[1:n + 1]))
    Max = None
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                v = a[i] + a[j] - a[k]
                if Max is None or v > Max:
                    Max = v
    print(Max)

Giải thích một số chỗ trong code:

1. 3 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);) giúp đẩy nhanh tốc độ nhập xuất khi code C++. Bài này input có thể lên tới 1 triệu số, số lượng lớn nên các bạn nhớ thêm 3 dòng này vào đầu hàm main nhé.
2. Đề không cho giới hạn giá trị các số trong mảng nên để chắc ăn mình chọn kiểu long long (số nguyên 8 byte, lưu được tới hơn 9 tỷ tỷ), yên tâm không sợ tràn số. Nếu theo thói quen dùng int (chỉ tới hơn 2 tỷ) thì lỡ có giá trị vượt quá là chương trình bị sai.
3. Mảng có thể lên tới 1 triệu số nên mình dùng vector thay vì mảng tĩnh. Kinh nghiệm: mảng tĩnh khai báo trong hàm chỉ nên chứa tối đa cỡ $3 \cdot 10^5$ phần tử, vượt ngưỡng này nên dùng mảng động để tránh tràn bộ nhớ.
4. Biến Max khởi tạo bằng LLONG_MIN (giá trị nhỏ nhất của long long) để giá trị đầu tiên đem so sánh chắc chắn lớn hơn nó mà cập nhật lại Max.
5. Max = max(Max, a[i] + a[j] - a[k]); là cách viết gọn của if(a[i] + a[j] - a[k] > Max) Max = a[i] + a[j] - a[k];. Hàm max(a, b) có sẵn trong C++, tương tự có hàm min.
6. Khi $n \lt 3$ thì không có bộ ba nào, code in ra 0 (giữ đúng như code gốc của mình).

Đá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^3)$ cho 3 vòng lặp lồng nhau. Theo quy tắc cộng Big-O lấy thành phần lớn nhất ⇒ $O(N^3)$.

Không gian$O(N)$

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

317 năm mới ra kết quả 😱

Với $N = 10^6$ thì $N^3 = 10^{18}$, vượt ngưỡng $10^8$ của 1 giây tới $10^{10}$ lần: trường hợp xấu nhất phải chạy cỡ 10 tỷ giây ⇔ khoảng 317 năm 😂. Ngay khi nghĩ ra ý tưởng này các bạn nhẩm độ phức tạp là biết không ổn rồi. Tuy nhiên mình vẫn khuyên: chưa nghĩ ra cách tối ưu thì cứ bỏ chút thời gian cài cách vét cạn này – rất dễ cài, chạy chậm nhưng luôn cho kết quả chính xác (nếu cài đúng). Ta sẽ dùng nó làm công cụ kiểm tra tính đúng cho cách tối ưu nghĩ ra về sau.

Cách 2Quy hoạch động: giữ 2 số lớn nhất phía trước – O(N)

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

Vì sao "Dãy số 1" là bài con của "Dãy số 2"?

Ở bài 1 ta chỉ làm việc trên 2 số $a_j - a_i$ để tìm hiệu lớn nhất. Bài này làm trên 3 số $a_i + a_j - a_k$. Nhưng nếu ta nhóm lại thành $(a_i + a_j) - a_k$ thì nó giống y như bài 1: cụm $(a_i + a_j)$ ở bài 2 đóng vai trò "số đứng trước", còn $a_k$ là "số đứng sau bị trừ". Bản chất vẫn quy về dạng tìm cặp giống bài 1 thôi.

Thêm một phần tử vào cuối thì có gì mới?

Vì $i \lt j \lt k$ nên mảng phải có tối thiểu 3 phần tử. Mảng có 3 phần tử a b c thì chỉ có 1 bộ ba duy nhất a b c, kết quả $a + b - c$. Khi mảng có thêm phần tử thứ 4 thành a b c d, các bộ ba là:

abc (đã có từ trước)

abd ← mới

acd ← mới

bcd ← mới

Mọi bộ ba mới sinh ra khi thêm d đều có d đứng cuối, tức là d luôn bị trừ đi; hai số được cộng chọn tuỳ ý trong các số đứng trước.

Điểm chung: phần tử mới d luôn đứng cuối – theo lẽ dĩ nhiên là vậy – nên nó chính là $a_k$ bị trừ đi, còn 2 số được cộng nằm trong các phần tử phía trước. Để biểu thức lớn nhất thì quy tắc toán học đơn giản: hai số được cộng nên là 2 số lớn nhất trong các phần tử đứng trước, vì 2 số lớn nhất cộng lại là tổng lớn nhất có thể. Việc trừ $a_k$ là bắt buộc, nhưng ta đảm bảo biểu thức lớn nhất nhờ $a_i + a_j$ là tổng 2 số lớn nhất.

Quy tắc

Đánh số từ 1, ta xét $k$ từ $3$ tới $N$. Với mỗi $k$: lấy 2 số lớn nhất trong $a_1, a_2, \ldots, a_{k-1}$ cộng lại rồi trừ $a_k$, so với Max để cập nhật. Xét xong $k = N$ thì Max chính là đáp án. Chỉ duyệt mảng một lần ⇒ $O(N)$.

Còn bạn nào đã biết quy hoạch động thì đây là 4 bước, y như những gì mình vừa nói nhưng tóm gọn lại:

1. Bài toán con: gọi $F[i]$ là giá trị biểu thức lớn nhất thu được khi số bị trừ là $a_i$ (bộ ba kết thúc tại $i$).
2. Bài toán cơ sở: $F[1], F[2]$ không tồn tại vì chưa đủ 3 phần tử thì không tính được biểu thức.
3. Đáp án: giá trị lớn nhất của các $F[i]$ với $i$ từ $3$ tới $N$.
4. Công thức truy hồi: $F[i] = \text{max1}(a_1, \ldots, a_{i-1}) + \text{max2}(a_1, \ldots, a_{i-1}) - a_i$, với max1 là giá trị lớn nhất, max2 là giá trị lớn nhì.

max1 và max2 phải là 2 phần tử khác nhau

Phải đảm bảo max1, max2 là 2 phần tử phân biệt, không có chuyện lấy cùng 1 phần tử rồi tính 2 lần. Còn giá trị thì có thể bằng nhau nếu giá trị lớn nhất xuất hiện nhiều hơn 1 lần (vd dãy 9 9 1 thì max1 = max2 = 9 là hoàn toàn hợp lệ).

Minh hoạ cập nhật Max1, Max2

Em nhập dãy rồi bấm Tiếp để xem với mỗi vị trí $k$, hai số lớn nhất phía trước (xanh) được cộng và $a_k$ (đỏ) bị trừ như thế nào:

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);
    cout.tie(0);
    int n;
    cin >> n;
    if(n < 3){
        cout << 0;
    }
    else{
        vector<long long> a(n + 1);
        for(int i = 1; i <= n; ++i){
            cin >> a[i];
        }
        long long Max1 = max(a[1], a[2]);
        long long Max2 = min(a[1], a[2]);
        long long Max = Max1 + Max2 - a[3];
        for(int i = 4; i <= n; ++i){
            if(a[i - 1] > Max1){
                Max2 = Max1;
                Max1 = a[i - 1];
            }
            else if(a[i - 1] > Max2){
                Max2 = a[i - 1];
            }
            Max = max(Max, Max1 + Max2 - a[i]);
        }
        cout << Max;
    }
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
if n < 3:
    print(0)
else:
    a = [0] + list(map(int, data[1:n + 1]))
    Max1 = max(a[1], a[2])
    Max2 = min(a[1], a[2])
    Max = Max1 + Max2 - a[3]
    for i in range(4, n + 1):
        if a[i - 1] > Max1:
            Max2 = Max1
            Max1 = a[i - 1]
        elif a[i - 1] > Max2:
            Max2 = a[i - 1]
        Max = max(Max, Max1 + Max2 - a[i])
    print(Max)

Bấm Tiếp để chạy tay từng dòng code C++ (phần "Dữ liệu" vẽ mảng a, tô xanh hai phần tử đang giữ vai trò Max1, Max2, tô vàng a[i] đang bị trừ):

C++▶ Chạy tay từng dòng codeCách 2: duyệt i từ 4 tới n, cập nhật Max1, Max2 bằng a[i-1] rồi so Max1 + Max2 - a[i] với Max.

Dữ liệu vào (stdin) – sửa thoải mái7 8 2 4 -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 cout.tie(0);

8 int n;

9 cin >> n;

10 if(n < 3){

11 cout << 0;

12 }

13 else{

14 vector<long long> a(n + 1);

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

16 cin >> a[i];

17 }

18 long long Max1 = max(a[1], a[2]);

19 long long Max2 = min(a[1], a[2]);

20 long long Max = Max1 + Max2 - a[3];

21 for(int i = 4; i <= n; ++i){

22 if(a[i - 1] > Max1){

23 Max2 = Max1;

24 Max1 = a[i - 1];

25 }

26 else if(a[i - 1] > Max2){

27 Max2 = a[i - 1];

28 }

29 Max = max(Max, Max1 + Max2 - a[i]);

30 }

31 cout << Max;

32 }

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Giải thích một số chỗ trong code:

1. Trong 4 bước quy hoạch động mình có gọi $F[i]$, nghe như cần thêm mảng $F$. Nhưng thực tế không cần: sau cùng ta chỉ cần giá trị lớn nhất của các $F[i]$, nên cứ vừa tính vừa so sánh cập nhật Max luôn, khỏi lưu từng $F[i]$ rồi duyệt lại.
2. Max1 lưu giá trị lớn nhất, Max2 lưu giá trị lớn nhì trong các phần tử trước vị trí i (hai biến có thể bằng nhau nếu giá trị lớn nhất xuất hiện nhiều lần). Ban đầu chúng là max và min của 2 số đầu, còn Max khởi tạo bằng bộ ba đầu tiên Max1 + Max2 - a[3].
3. Vòng lặp bắt đầu từ i = 4. Mỗi lượt ta đưa a[i - 1] vào xét trước (vd i = 4 thì phải xét thêm a[3], vì ban đầu mới xét a[1], a[2]). Nếu a[i - 1] > Max1 thì nó lên làm số lớn nhất – nhưng trước khi gán, ta chuyển Max1 hiện tại xuống cho Max2, để Max2 vẫn là số lớn nhất theo sau Max1, không có giá trị nào chen giữa. Còn nếu chỉ lớn hơn Max2 thì cập nhật Max2 = a[i - 1].
4. Cập nhật xong Max1, Max2 mới tính Max1 + Max2 - a[i] và so với Max. Kết thúc vòng lặp, Max là giá trị biểu thức lớn nhất.

Đá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)$ xử lý, tức $O(2N)$; bỏ hằng số ⇒ $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

O(N) là tốt nhất có thể

Bài có mảng $N$ phần tử thì chắc chắn phải đọc mảng vào rồi mới xử lý, riêng việc đọc đã tốn $O(N)$, nên không thể có độ phức tạp nào tốt hơn. Với $N = 10^6$, ít hơn ngưỡng $10^8$ cả 100 lần ⇒ yên tâm không sợ TLE.

Cách 3Không cần mảng: đọc tới đâu xử lý tới đó – O(N), bộ nhớ O(1)

Đến đây thì đã được rồi, nhưng mình trình bày luôn một cách tối ưu hơn nữa: không cần bộ nhớ cho mảng $a$, độ phức tạp không gian chỉ còn $O(1)$ vì chỉ cần vài biến đơn lẻ. Thời gian vẫn $O(N)$ nhưng chỉ cần một vòng lặp duy nhất gộp cả quá trình đọc dữ liệu lẫn xử lý.

Để ý ở cách 2, tại mỗi bước ta chỉ đụng tới đúng 2 phần tử: a[i - 1] (để cập nhật Max1, Max2) và a[i] (để trừ). Vậy chỉ cần một biến c: lúc đầu vòng lặp c đang giữ số vừa đọc trước đó (chính là a[i - 1]) → dùng nó cập nhật Max1, Max2; sau đó cin >> c đọc số mới (chính là a[i]) → tính Max1 + Max2 - c. Ba số đầu đọc riêng vào a, b, c, nên vòng lặp còn chạy n - 3 lần.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    if(n < 3){
        cout << 0;
    }
    else{
        long long a, b, c;
        cin >> a >> b >> c;
        long long Max1 = max(a, b);
        long long Max2 = min(a, b);
        long long Max = Max1 + Max2 - c;
        n -= 3;
        while(n--){
            if(c > Max1){
                Max2 = Max1;
                Max1 = c;
            }
            else if(c > Max2){
                Max2 = c;
            }
            cin >> c;
            Max = max(Max, Max1 + Max2 - c);
        }
        cout << Max;
    }
    return 0;
}

import sys

it = iter(sys.stdin.buffer.read().split())
n = int(next(it))
if n < 3:
    print(0)
else:
    a, b, c = int(next(it)), int(next(it)), int(next(it))
    Max1 = max(a, b)
    Max2 = min(a, b)
    Max = Max1 + Max2 - c
    for _ in range(n - 3):
        if c > Max1:
            Max2 = Max1
            Max1 = c
        elif c > Max2:
            Max2 = c
        c = int(next(it))
        Max = max(Max, Max1 + Max2 - c)
    print(Max)

Tư tưởng xử lý y như cách 2, chỉ là tối ưu lại không cần mảng và gộp chung đọc dữ liệu + xử lý. Hiểu được cách 2 rồi thì cách này mình tin sẽ không có gì khó hiểu cả 😉.

Không gian$O(1)$

Thời gian$O(N)$

Luyện tư duy giải thuật quan trọng thế nào?

Từ cách ban đầu cần mảng và $O(N^3)$, trường hợp xấu nhất ước tính 317 năm mới chạy xong, tới cách sau cùng không cần mảng mà cùng trường hợp đó chớp mắt cái là xong. Trong khi đối chiếu lại thì code chẳng dài thêm bao nhiêu so với cách ban đầu cả. Thế mới thấy luyện tốt kiến thức giải thuật hay thế nào đúng không 😄

Lưu ý với Python

Bản Python ở trên đọc toàn bộ input một lần bằng sys.stdin.buffer.read() cho nhanh, nên thực tế vẫn giữ danh sách các token trong bộ nhớ. Với $N = 10^6$, bản Python của cách 2 và cách 3 chạy khoảng 1.2–1.3 giây trên máy mình, có thể vượt giới hạn 1 giây tuỳ hệ thống chấm; nếu bị TLE thì các bạn nộp bằng C++ nhé.

Ghi chú của mình: code C++ và Python của cả 3 cách đều cho đúng ví dụ của đề, và đã được so với một chương trình vét cạn độc lập (thử mọi bộ ba $i \lt j \lt k$) trên 600 bộ test ngẫu nhiên ($n$ từ 1 tới 9, giá trị tới $\pm 10^{12}$, có cả số âm) – khớp hết. Với $n = 10^6$ (giá trị tới $\pm 10^9$): C++ cách 2 chạy khoảng 0.19 giây, cách 3 khoảng 0.14 giây. Còn cách 1 với $n = 1000$ đã mất khoảng 0.3 giây, đúng như phân tích $O(N^3)$.

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 😇