Elearning CodePath – CTP Online Judge

Tổng Lớn Nhất Không Kề Nhau

GEN006

🟢 Hard #Dynamic Programming

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy số gồm $N$ phần tử $A = (A_1, A_2, \dots, A_N)$.

Yêu cầu: Tìm **tổng lớn nhất** của một tập hợp con các phần tử trong dãy $A$ sao cho không có hai phần tử nào trong tập hợp con đó **kề nhau** trong dãy ban đầu.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `BAI4.INP`:

* Dòng đầu chứa số nguyên $N$.
* Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$.

Giới hạn: $1 \le N \le 10^5$, $1 \le A_i \le 10^6$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `BAI4.OUT` một số nguyên duy nhất — tổng lớn nhất mà không chọn hai phần tử kề nhau.

---
### ✨ Ví dụ

| Input (`BAI4.INP`) | Output (`BAI4.OUT`) |
| :--- | :--- |
| `6` <br> `3 2 7 10 12 7` | `29` |

Giải thích: Tập hợp được chọn là $\{3, 7, 12\}$. Tổng $3 + 7 + 12 + 7 = 22$.
$3, 2, 7, 10, 12, 7$
* Chọn $A_1=3$.
* Bỏ $A_2=2$.
* Chọn $A_3=7$. (Tổng: $3+7=10$).
* Bỏ $A_4=10$.
* Chọn $A_5=12$. (Tổng: $10+12=22$).
* Bỏ $A_6=7$.
    Tổng: $22$.

### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính | 
| :--- | :--- | :--- | 
| 1 | $N \le 25$ | $50\%$ | 
| 2 | $N \le 1000$ | $30\%$ | 
| 3 | $N \le 10^5$ | $20\%$ |

✅ Đã AC: 4 / 13 submissions