Phân tích

Ta cần chọn một ngày mua đứng trước ngày bán. Với mỗi ngày bán, điều tốt nhất ta có thể làm là mua ở giá nhỏ nhất đã xuất hiện trước đó.

Vì thế, khi duyệt mảng từ trái sang phải, ta chỉ cần lưu:

• min_price: giá nhỏ nhất đã thấy đến thời điểm hiện tại
• best_profit: lợi nhuận lớn nhất đã tính được

Ở mỗi giá price:

1. Xem nếu bán ở ngày này thì lợi nhuận là price - min_price
2. Cập nhật best_profit
3. Cập nhật lại min_price nếu price nhỏ hơn

Nếu mảng giảm hoàn toàn thì mọi hiệu số đều không dương, khi đó đáp án vẫn là 0.

Thuật toán

1. Gán min_price = a_1, best_profit = 0
2. Duyệt các phần tử còn lại trong mảng:
   • cập nhật best_profit = max(best_profit, a_i - min_price)
   • cập nhật min_price = min(min_price, a_i)
3. In best_profit

Độ phức tạp

• Thời gian: ~O(n)~
• Bộ nhớ: ~O(1)~

Code mẫu

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

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

    int n;
    cin >> n;

    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    long long min_price = a[0];
    long long best_profit = 0;

    for (int i = 1; i < n; ++i) {
        best_profit = max(best_profit, a[i] - min_price);
        min_price = min(min_price, a[i]);
    }

    cout << best_profit << '\n';
    return 0;
}