Elearning CodePath – CTP Online Judge

Tổng Dãy Con Liên Tiếp Lớn Nhất

MAXSUB

🟢 Easy #General #Greedy

### 📝 Bài toán
Cho một mảng số nguyên A gồm n phần tử a1, a2, ..., an.
Yêu cầu: Tìm một dãy con liên tiếp của mảng A sao cho tổng các phần tử trong dãy con đó là lớn nhất.
Lưu ý: Dãy con phải có ít nhất một phần tử.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file MAXSUB.INP:
* Dòng đầu tiên chứa số nguyên n là số lượng phần tử của mảng.
* Dòng thứ hai chứa n số nguyên a1, a2, ..., an.

Giới hạn:
* 1 <= n <= 10^6
* |ai| <= 10^9

### 📤 Định dạng Đầu ra
Ghi ra file MAXSUB.OUT một số nguyên duy nhất là tổng lớn nhất tìm được.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 7 | 11 |
| 2 3 -8 7 -1 2 3 | |

Giải thích:
* Dãy con [7, -1, 2, 3] có tổng là 7 + (-1) + 2 + 3 = 11 là tổng lớn nhất.

### 🏷 Subtasks
| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | n <= 500 | 30% |
| 2 | n <= 5000 | 20% |
| 3 | n <= 10^6 | 50% |

✅ Đã AC: 5 / 15 submissions