Tổng Đoạn Con Lớn Nhất

Cho một mảng $n$ số nguyên. Hãy tìm tổng lớn nhất của một đoạn con liên tiếp không rỗng.

Dữ liệu vào

• Dòng 1: số nguyên $n$
• Dòng 2: $n$ số nguyên $x_1,x_2,\dots ,x_n$

Dữ liệu ra

In ra một số nguyên — tổng lớn nhất của đoạn con liên tiếp.

Ràng buộc

• $1\le n\le 2\times {10}^5$
• $-{10}^9\le x_i\le {10}^9$

Ví dụ