Cho một mảng gồm n số nguyên. Hãy tìm tổng lớn nhất của một dãy con liên tiếp không rỗng (subarray) trong mảng.
Ví dụ với mảng [-2, 1, -3, 4, -1, 2, 1, -5, 4], dãy con [4, -1, 2, 1] có tổng 6 là lớn nhất.
Gợi ý: sử dụng thuật toán Kadane với độ phức tạp O(n).
Dòng đầu chứa số nguyên n. Dòng thứ hai chứa n số nguyên cách nhau bởi dấu cách.
1≤n≤105, −104≤ai≤104
In ra một số nguyên là tổng lớn nhất của một dãy con liên tiếp.
Ví dụ:
Đầu vào:
9
-2 1 -3 4 -1 2 1 -5 4
Đầu ra:
6
Giải thích:
Đang tải editor...