Tìm đoạn con liên tiếp có tổng lớn nhất trong mảng gồm \(N\) số nguyên.

Định dạng đầu vào

• Dòng 1: \(N\) (\(1 \le N \le 10^5\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(|a_i| \le 10^9\)).

Định dạng đầu ra

• In ra tổng lớn nhất của một đoạn con không rỗng.

Ví dụ

Input:

5
-2 1 -3 4 -1

Output:

4

Giải thích: Đoạn con \([4]\) có tổng lớn nhất là 4.

Ràng buộc & Subtasks