Đề bài:

Cho một mảng gồm ~ n ~ số nguyên, nhiệm vụ của bạn là tìm tổng lớn nhất của một dãy con liên tiếp (contiguous subarray).

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên ~ n ~: kích thước của mảng.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các giá trị của mảng.

Dữ liệu ra:

• In ra một số nguyên: tổng lớn nhất của dãy con liên tiếp.

Ràng buộc:

• ~ 1 \leq n \leq 2 \cdot 10^5 ~
• ~ -10^9 \leq x_i \leq 10^9 ~

Ví dụ:

Input:

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

Output:

9

Giải thích:

• Dãy con liên tiếp có tổng lớn nhất là ~ [3, -2, 5, 3] ~, với tổng ~ 3 + (-2) + 5 + 3 = 9 ~.