Đoạn tổng lớn
Xem dưới dạng PDF
Gửi bài giải
Điểm:
100
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Kiểu bài tập
Bình có một dãy số gồm \(N\) phần tử. An muốn chọn một đoạn con liên tiếp (dãy con gồm các phần tử đứng cạnh nhau) sao cho tổng các phần tử trong đoạn là lớn nhất có thể.
Hãy giúp An tìm tổng lớn nhất đó.
Ràng buộc
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 30 | Các giá trị nhỏ |
| 2 | 30 | \(N \le 10^5\) |
| 3 | 40 | Không có ràng buộc gì thêm |
Dữ liệu
- Dòng đầu: số nguyên \(N\)
- Dòng thứ hai: \(N\) số nguyên \(a_1, a_2, ..., a_N\)
Kết quả
Một số nguyên duy nhất là tổng lớn nhất của một đoạn con liên tiếp.
Giới hạn
| Mức | \(N\) | Điểm |
|---|---|---|
| 1 | \(\le 10\) | 20 |
| 2 | \(\le 100\) | 20 |
| 3 | \(\le 10^4\) | 30 |
| 4 | \(\le 10^5\) | 30 |
Nhận xét