Elearning CodePath – CTP Online Judge

Hiệu lớn nhất giữa hai phần tử

DIFFMAX

🟢 Medium #Greedy #Dynamic Programming

### 📌 Thông tin chung

---
Cho một mảng số nguyên $A = [a_1, a_2, \dots, a_n]$ gồm $n$ số nguyên. 
Ta định nghĩa: $Diff(A) = \max(a_j - a_i)$ với $1 \le i \le j \le n$.
Nghĩa là, bạn cần tìm hiệu lớn nhất giữa hai phần tử $a_j - a_i$ trong mảng, với điều kiện chỉ số $i$ phải nhỏ hơn hoặc bằng chỉ số $j$ ($i \le j$).

Yêu cầu: Tính giá trị lớn nhất của hiệu này.

---
### 📥 Dữ liệu vào

* Dòng 1: Số nguyên $n$ ($1 \le n \le 10^5$) là số phần tử của mảng.
* Dòng 2: Gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^9$).

---
### 📤 Kết quả

Một số nguyên duy nhất là giá trị lớn nhất của $a_j - a_i$ thỏa mãn $1 \le i \le j \le n$.

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `5` <br> `3 1 2 4 7` | `6` |

**Giải thích Ví dụ:**
Trong mảng $[3, 1, 2, 4, 7]$, hiệu lớn nhất là $a_5 - a_2 = 7 - 1 = 6$ (với $i=2, j=5$ và $i \le j$).

---
### 🏷 Subtasks

| \# | Điểm | Ràng buộc $N$ | 
| :---: | :---: | :--- | 
| $1$ | $30\%$ | $N \le 2000$ | 
| $2$ | $70\%$ | $N \le 10^5$ |

---

✅ Đã AC: 3 / 6 submissions