Tìm dãy con có tổng lớn nhất
Đề bài
Cho dãy gồm n số nguyên (có thể âm). Tìm tổng lớn nhất của một dãy con liên tiếp (Maximum Subarray — Kadane).
Dữ liệu vào
Dòng 1: n (1 ≤ n ≤ 10^5).
Dòng 2: n số nguyên.
Dữ liệu ra
Một số nguyên — tổng lớn nhất của dãy con liên tiếp.
Ví dụ
| Input | Output |
|---|---|
| 5 -2 1 -3 4 -1 2 1 -5 4 |
6 |
| 3 -1 -2 -3 |
-1 |
Nhận xét