Hiểu bài toán

Bài toán yêu cầu tìm lợi nhuận tối đa có thể đạt được bằng cách mua và bán cổ phiếu trong n ngày với giá mua/bán là a[i] vào ngày i. Các thao tác được phép trong một ngày: mua 1 cổ phiếu, bán một số lượng cổ phiếu bất kỳ bạn đang có, hoặc không làm gì. Lợi nhuận = tổng tiền bán - tổng tiền mua. Điều này khác với bài toán stock classic (mỗi lần chỉ mua hoặc bán 1 cổ phiếu) ở chỗ bạn có thể bán ra một số lượng lớn cổ phiếu đã tích lũy được trước đó. Ví dụ, nếu bạn mua 100 cổ phiếu ở các ngày trước, bạn có thể bán cả 100 cổ phiếu đó trong một ngày để chốt lời/giảm lỗ.

Các cách tiếp cận

Cách Giải thuật tham lam (Duyệt ngược)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        ll res = 0;
        int max_price = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (a[i] > max_price) {
                max_price = a[i];
            } else {
                res += (ll)(max_price - a[i]);
            }
        }

        cout << res << "\n";
    }

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất và cũng là cách giải quyết trực quan nhất cho biến thể bài toán này.

Logic: Hãy suy nghĩ từ tương lai về quá khứ. Vào một ngày bất kỳ, nếu chúng ta biết rằng trong tương lai (phía sau ngày đó) sẽ có một ngày giá cổ phiếu cao hơn giá hiện tại, tại sao không mua ngay hôm nay và bán vào ngày mai có giá cao hơn? Do ta có thể bán bất kỳ số lượng nào, ta có thể mua 1 cổ phiếu mỗi ngày khi thấy giá rẻ và bán tất cả vào ngày giá cao nhất tiếp theo.

Thuật toán:

1. Duyệt mảng giá từ cuối lên đầu (ngày n-1 về ngày 0).
2. Duy trì biến max_price là giá cao nhất tìm được từ ngày hiện tại đến ngày cuối cùng.
3. Nếu a[i] < max_price: Tức là có thể mua vào ngày i và bán được giá cao hơn trong tương lai. Ta cộng dồn lợi nhuận (max_price - a[i]) vào kết quả.
4. Nếu a[i] >= max_price: Tức là đây là đỉnh giá mới từ đây trở đi. Cập nhật max_price = a[i].

Ví dụ test 2 (1, 2, 100):

• Duyệt ngược: Ngày 3 (giá 100). max_price = 100.
• Ngày 2 (giá 2): 2 < 100 => Lợi nhuận += 98. max_price vẫn là 100.
• Ngày 1 (giá 1): 1 < 100 => Lợi nhuận += 99. max_price vẫn là 100.
• Tổng = 197.

Lưu ý: Code mẫu dùng if (a[i] < max_price) res += max_price - a[i]; else max_price = a[i];. Logic này đúng vì nếu a[i] == max_price, ta không cần mua (mua xong bán ngay không có lãi), và ta không cần cập nhật max_price (vì giá trị không thay đổi), nhưng để an toàn thì else bao gồm cả trường hợp bằng.

Cách Quy hoạch động (Tham số phụ)

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

int t;

void Case() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // f[i] là tổng giá trị max_price từ ngày i đến n-1
    //累加 (prefix sum) của max_price
    vector<int> suffix_max(n);
    suffix_max[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        suffix_max[i] = max(suffix_max[i + 1], a[i]);
    }

    // Lợi nhuận = sum(suffix_max[i] - a[i]) voi i tu 0 den n-1
    // Tuy nhiên, có thể chỉ mua bán 1 đoạn
    // Công thức trong code gốc: ans = max(f[n] - f[i-1] - (ps[n] - ps[i-1]))
    // Tức là tìm đoạn [i, n] tối ưu.
    // Thực tế bài này mua bán tự do nên mua toàn bộ đoạn có lãi là tối ưu.

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (suffix_max[i] > a[i]) {
            res += suffix_max[i] - a[i];
        }
    }
    cout << res << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) Case();
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận dựa trên Quy hoạch động hoặc tiền xử lý.

Logic: Mục tiêu là xác định cho mỗi ngày i, giá cao nhất có thể bán được nếu mua vào ngày i. Ta gọi giá này là max_sell[i].

Thuật toán:

1. Tạo mảng suffix_max (mảng max giá trị từ phải sang trái).
   • suffix_max[i] = max(a[i], a[i+1], ..., a[n-1]).
   • Cách tính: suffix_max[n-1] = a[n-1]. Duyệt từ n-2 về 0: suffix_max[i] = max(suffix_max[i+1], a[i]).
2. Tính lợi nhuận: Duyệt từ 0 đến n-1, nếu a[i] < suffix_max[i] thì cộng dồn suffix_max[i] - a[i] vào kết quả.

Độ phức tạp:

• Thời gian: O(N) để xây dựng mảng suffix max + O(N) để tính toán tổng.
• Không gian: O(N) để lưu mảng.

So với cách tham lam (Solution 1), cách này dùng nhiều bộ nhớ hơn nhưng logic tương đương.

Cách Giải pháp QHĐ cơ bản (Cổ điển)

// Code minh họa logic QHĐ (không phải code tối ưu cho bài này)
// Chỉ để minh họa cách suy nghĩ khác biệt
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        vector<int> a(n);
        for(int i=0; i<n; i++) cin >> a[i];

        long long ans = 0;
        // Logic tham lam greedily tối ưu O(N)
        // Hoặc dùng stack (O(N)) để tìm Next Greater Element
        // Nhưng NLE không cần thiết ở đây vì có thể bán rải rác.

        // Dưới đây là cách chuyển đổi bài toán thành: 
        // Lợi nhuận = (Tổng giá trị max tương lai) - (Tổng giá mua)
        long long max_val = 0;
        for(int i = n-1; i >= 0; i--) {
            max_val = max((long long)a[i], max_val);
            ans += max_val - a[i];
        }
        cout << ans << endl;
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Nếu chỉ áp dụng bài toán stock classic (mua 1 bán 1, không được giữ quá 1 cổ phiếu), ta cần dùng Dynamic Programming với 2 trạng thái:

• dp[i][0]: Lợi nhuận tối đa đến ngày i với trạng thái không giữ cổ phiếu.
• dp[i][1]: Lợi nhuận tối đa đến ngày i với trạng thái có giữ 1 cổ phiếu.

Tuy nhiên, bài toán này khác biệt ở chỗ "Bán ra một số lượng cổ phiếu nào đó". Điều này loại bỏ giới hạn 1 cổ phiếu.

Vì vậy, bài toán này về bản chất là: "Tìm mọi cơ hội mua vào ngày i và bán vào ngày j > i sao cho a[j] > a[i]. Vì có thể bán bao nhiêu tùy ý, ta có thể mua 1 cổ phiếu mỗi ngày giá rẻ và bán tất cả vào ngày giá cao nhất".

Do đó, các giải pháp QHĐ phức tạp cho bài toán classic không cần thiết và Solution 1 (Tham lam duyệt ngược) là tối ưu nhất.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này khác với 'Best Time to Buy and Sell Stock II' (LeetCode) ở chỗ: LeetCode II chỉ bán được 1 cổ phiếu/ngày, còn bài này có thể bán số lượng lớn. Do đó, ta có thể mua 1 đơn vị mỗi ngày khi thấy giá rẻ và bán tất cả vào ngày giá cao nhất.
• Thuật toán 'Duyệt ngược - Greedy': Duyệt từ cuối lên đầu, giữ lại giá cao nhất thấy được. Nếu gặp ngày có giá thấp hơn giá cao nhất đó, ta chắc chắn có lãi nếu mua ngày đó và bán ở giá cao nhất sau đó.
• Bài toán quy hoạch động kinh điển (mua 1 bán 1/lưu trữ 1 cổ phiếu) là sai lệch với yêu cầu đề bài này do giới hạn số lượng bán.

Lỗi thường gặp

• Sử dụng thuật toán cho bài toán 'Best Time to Buy and Sell Stock II' (LeetCode): Thuật toán đó chỉ cộng dồn chênh lệch giữa ngày sau và ngày trước (max(0, a[i+1] - a[i])). Nó chỉ đúng nếu mỗi ngày chỉ được mua/bán tối đa 1 cổ phiếu. Nó sẽ sai đối với bài này (ví dụ: 1, 3, 1, 2, LeetCode II được 3, bài này được 3, nhưng 1, 2, 100: LeetCode II được 99, bài này được 197).
• Lỗi kiểu dữ liệu: Giá trị a[i] lên tới 100,000 và n lên tới 50,000. Lợi nhuận tối đa có thể là 50,000 * 100,000 = 5*10^9, vượt quá giới hạn của int (2*10^9). Phải dùng long long (C++) hoặc long (Java).
• Logic nhầm lẫn với bài toán 'mua 1 bán 1 nhiều lần': Nhiều người sẽ tìm các điểm trough (đáy) và peak (đỉnh) để giao dịch, hoặc dùng max(0, a[i+1] - a[i]). Cách này không tối ưu vì nó không cho phép tích lũy số lượng lớn cổ phiếu ở các ngày giá rẻ để bán cùng lúc ở ngày giá cao.