Mua thấp bán cao
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề 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:
- Mua đúng $1$ cổ phiếu với giá $p_i$.
- 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).
- 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$
Community Discussion