Cho một mảng gồm số nguyên (có thể có số âm). Một dãy con liên tiếp là một dãy các phần tử liền kề nhau trong mảng.
Yêu cầu tìm và in ra tổng lớn nhất của một dãy con liên tiếp bất kỳ trong mảng . Dãy con rỗng có tổng là .
Dữ liệu:
- Dòng đầu tiên chứa số nguyên .
- Dòng thứ hai chứa số nguyên .
Kết quả: Một số nguyên duy nhất là tổng lớn nhất tìm được.
Ví dụ:
Dữ liệu:
8
-1 3 -2 5 3 -5 2 2
Kết quả:
Giải thích: Dãy con liên tiếp có tổng lớn nhất là với tổng là .
Giới hạn:
