Bài 7.5. Tối Ưu Lợi Nhuận Giao Dịch Cổ Phiếu - [Độ khó: Khó]

Mô tả bài tập: Bạn là một nhà đầu tư mới tham gia thị trường chứng khoán ảo và muốn thử sức với việc mua bán cổ phiếu để kiếm lời. Bạn được cung cấp lịch sử giá của một loại cổ phiếu trong N ngày liên tiếp. Mục tiêu của bạn là tìm ra cách mua và bán cổ phiếu một lần duy nhất để đạt được lợi nhuận cao nhất có thể. Bạn phải mua trước khi bán (tức là ngày mua phải trước hoặc bằng ngày bán, nhưng giá bán phải cao hơn giá mua để có lời). Nếu không có cách nào để kiếm lời (giá luôn giảm hoặc không đổi, hoặc không có cặp mua/bán nào có lời), lợi nhuận tối đa sẽ là 0.

INPUT FORMAT

Dữ liệu đầu vào gồm hai dòng:

• Dòng 1: Một số nguyên N (1 <= N <= 100,000) - Số ngày có dữ liệu giá.
• Dòng 2: N số nguyên p_1, p_2, ..., p_N (1 <= p_i <= 100,000) - Giá của cổ phiếu vào ngày thứ i. Các số cách nhau bởi dấu cách.

OUTPUT FORMAT

In ra một số nguyên duy nhất là lợi nhuận tối đa có thể đạt được.

Ví dụ:

Input:

6
7 1 5 3 6 4

Output:

5

Giải thích:

• Có 6 ngày với giá cổ phiếu lần lượt là: 7, 1, 5, 3, 6, 4.
• Để đạt lợi nhuận tối đa, chúng ta cần tìm giá mua thấp nhất trước và giá bán cao nhất sau nó.
• Nếu mua vào ngày có giá 7, lợi nhuận tối đa là 7 - 7 = 0 (tự bán luôn) hoặc 4 - 7 = -3 (bán giá 4).
• Nếu mua vào ngày có giá 1 (ngày thứ 2):
  • Bán vào ngày giá 5 (ngày thứ 3): Lợi nhuận 5 - 1 = 4.
  • Bán vào ngày giá 3 (ngày thứ 4): Lợi nhuận 3 - 1 = 2.
  • Bán vào ngày giá 6 (ngày thứ 5): Lợi nhuận 6 - 1 = 5.
  • Bán vào ngày giá 4 (ngày thứ 6): Lợi nhuận 4 - 1 = 3.
• So sánh các lợi nhuận có thể có (bao gồm cả trường hợp mua vào ngày khác), lợi nhuận cao nhất đạt được là 5, khi mua vào ngày giá 1 và bán vào ngày giá 6.

Ví dụ 2 (Edge Case - không có lợi nhuận):

Input:

5
9 8 7 6 5

Output:

0

Giải thích:

• Giá cổ phiếu liên tục giảm. Không có cách nào mua trước bán sau để có lời. Lợi nhuận tối đa là 0.