Tổng lớn nhất của dãy con
Mô tả
Cho dãy gồm n số nguyên. Tìm tổng lớn nhất của một dãy con liên tiếp không rỗng.
Input
Dòng đầu là n. Dòng thứ hai gồm n số nguyên.
Output
In ra tổng lớn nhất tìm được.
Ví dụ
Input
5
-2 3 -1 5 -4
Output
7
Thuật toán Kadane duyệt dãy một lần. Tại mỗi vị trí, ta chọn bắt đầu dãy con mới từ phần tử hiện tại hoặc nối phần tử đó vào dãy con tốt nhất đang có.
Code Editor
Code đã được lưu trên trình duyệt. Hệ thống chấm test tự động sẽ hoạt động sau khi kết nối máy chủ Judge.