Mua thấp bán cao

Buổi 12 — Greedy Algorithm greedy
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Bạn biết trước giá của một loại cổ phiếu trong $N$ ngày tới, ngày thứ $i$ có giá là $p_i$. Ban đầu bạn không nắm giữ cổ phiếu nào và có đủ tiền để mua bất cứ lúc nào. Tại mỗi ngày $i$, bạn có thể chọn một trong ba hành động sau:

  1. Mua đúng $1$ cổ phiếu với giá $p_i$.
  2. Bán đúng $1$ cổ phiếu đang nắm giữ với giá $p_i$ (nếu đang có ít nhất $1$ cổ phiếu).
  3. Không làm gì cả.

Sau ngày thứ $N$, bạn không còn nhu cầu giữ cổ phiếu nữa. Hãy tìm tổng lợi nhuận tối đa bạn có thể thu được.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $p_1, p_2, \dots, p_N$.
Dữ liệu ra

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

Ví dụ
Input Output
9\n10 5 4 7 9 12 6 2 10 20
5\n5 4 3 2 1 0
Giới hạn
  • $1 \le N \le 3 \cdot 10^5$
  • $1 \le p_i \le 10^6$
Draft saved