Elearning CodePath – CTP Online Judge

SIÊU CỔ PHIẾU

DOUBLE_STOCK

🟢 Easy

**Tên bài:** SIÊU CỔ PHIẾU
**Thời gian chạy:** 1.0s | **Bộ nhớ:** 256MB

### 📝 Bài toán
Thị trường chứng khoán đang biến động mạnh. Bạn được cho dãy $A$ gồm $n$ phần tử là giá cổ phiếu trong $n$ ngày. Lần này, sàn giao dịch cho phép bạn thực hiện tối đa 2 lần giao dịch (mỗi lần gồm 1 lượt mua và 1 lượt bán).

**Điều kiện:**
1. Hai lần giao dịch này không được giao nhau (tức là bạn phải bán xong lần 1 mới được mua lần 2).
2. Trong mỗi lần giao dịch, ngày bán phải sau ngày mua ($j > i$).
3. Bạn có thể chọn chỉ giao dịch 1 lần hoặc không giao dịch lần nào nếu thị trường quá tệ.

**Yêu cầu:** Tìm tổng lợi nhuận lớn nhất có thể đạt được từ 2 lần giao dịch đó.

### 📥 Input
* Dòng 1: Số nguyên $n$ ($2 \le n \le 10^5$).
* Dòng 2: $n$ số nguyên $a_i$ ($1 \le a_i \le 10^9$).

### 📤 Output
* Một số nguyên duy nhất là tổng lợi nhuận tối đa.

### 💡 Ví dụ
**Input:**
```
8
3 3 5 0 0 3 1 4
```
**Output:**
```
6
```
*(Giải thích: 
- Lần 1: Mua giá 3 (ngày 1), bán giá 5 (ngày 3). Lãi = 2.
- Lần 2: Mua giá 0 (ngày 4 hoặc 5), bán giá 4 (ngày 8). Lãi = 4.
Tổng lãi = 2 + 4 = 6).*

✅ Đã AC: 6 / 9 submissions