Maximum Subarray Sum

Bài toán

Cho một mảng số nguyên arr gồm n phần tử, hãy tìm tổng lớn nhất của một dãy con liên tiếp trong mảng.

Input Format

Một mảng arr gồm n số nguyên (\(n \ge 1\)), với:

Constraints

• Mảng có ít nhất một phần tử.
• Giải thuật cần có độ phức tạp tối ưu \(O(n)\) (sử dụng thuật toán Kadane).

Output Format

Trả về một số nguyên là tổng lớn nhất của một dãy con liên tiếp trong mảng.

Examples

Input 0

1 2 3 -2 5

Output 0

9

Input 1

-1 -2 -3 -4

Output 1

-1