Elearning CodePath – CTP Online Judge

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

CIRSUB

🟢 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. Vì đây là dãy vòng, nên sau phần tử an sẽ quay trở lại phần tử a1.
Yêu cầu: Tìm một dãy con liên tiếp (có thể đi qua điểm nối từ an về a1) 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ử và không được chứa một phần tử của mảng gốc quá một lần (độ dài dãy con <= n).

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file CIRSUB.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 CIRSUB.OUT một số nguyên duy nhất là tổng lớn nhất tìm được.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 7 | 22 |
| 8 -8 9 -9 10 -11 12 | |

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

✅ Đã AC: 4 / 20 submissions