Maximum Subarray Sum

Mô tả

Tìm tổng lớn nhất của một dãy con liên tiếp trong mảng số nguyên (thuật toán Kadane).

Input Format

Dòng 1: n.
Dòng 2: n số nguyên.

Constraints

1 ≤ n ≤ 1000
-1000 ≤ arr[i] ≤ 1000

Sample Input

8
-2 1 -3 4 -1 2 1 -5 4

Sample Output

6