Lợi nhuận tối đa một giao dịch

Hướng tiếp cận

Ta cần tìm cặp chỉ số $(i,j)$ với $i\le j$ sao cho $p_j-p_i$ lớn nhất. Cách "brute" duyệt mọi cặp tốn $O(n^2)$, không khả thi khi $n$ tới $2·{10}^5$ và tổng $n$ tới ${10}^6$.

Quan sát: khi ta cố định ngày bán $j$, lợi nhuận tối ưu sẽ đạt được khi $p_i$ là giá nhỏ nhất trong tiền tố $p_1,\dots ,p_j$. Vì vậy chỉ cần duy trì giá nhỏ nhất tiền tố ($\text{pmin}$) là đủ.

Nhận xét quan trọng

• Điều kiện $i\le j$ là mấu chốt. Nếu bỏ qua điều kiện này, ta sẽ ra $max(p)-min(p)$, có thể sai khi $max$ xảy ra trước $min$.
• Khi mọi lợi nhuận đều âm/không, đáp án là $0$ (không giao dịch), không phải số âm.
• Có thể chọn $i=j$ cho lợi nhuận $0$, nên đáp án luôn $\ge 0$.

Thuật toán

Khởi tạo $\text{pmin}=p_1$, $\text{ans}=0$. Duyệt $j$ từ $2$ đến $n$:

1. Cập nhật $\text{ans}=max(\text{ans},p_j-\text{pmin})$.
2. Cập nhật $\text{pmin}=min(\text{pmin},p_j)$.

Lưu ý thứ tự: phải tính $\text{ans}$ trước (dùng $\text{pmin}$ của tiền tố $[1,j-1]$), rồi mới cập nhật $\text{pmin}$ với $p_j$ (cho lần sau). Nếu cập nhật $\text{pmin}$ trước thì cũng đúng vì $p_j-p_j=0$ không làm xấu kết quả, nhưng cách viết "tính trước, cập nhật sau" rõ ràng hơn.

In ra $\text{ans}$.

Độ phức tạp

• Thời gian: $O(n)$ cho mỗi test, tổng $O(\sum n)$ — tối đa ${10}^6$ phép cộng/so sánh.
• Bộ nhớ: $O(n)$ để đọc dãy (hoặc $O(1)$ nếu đọc và xử lý online).