Tổng dãy con lớn nhất

Trong một buổi học, giảng viên đã đưa ra một bài toán thú vị cho FullHouse Dev. Họ được yêu cầu tìm tổng lớn nhất của một dãy con liên tiếp trong một mảng số nguyên. Với tinh thần ham học hỏi, FullHouse Dev đã bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của FullHouse Dev là tìm tổng lớn nhất của các giá trị trong một dãy con liên tiếp, không rỗng.

INPUT FORMAT:

• 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, \dots, x_n\): các giá trị trong mảng.

OUTPUT FORMAT:

• In ra một số nguyên: tổng dãy con lớn nhất.

Ràng buộc:

• \(1 \le n \le 2 \cdot 10^5\)
• \(-10^9 \le x_i \le 10^9\)

Ví dụ

INPUT

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

OUTPUT

9

Giải thích

Trong ví dụ này, dãy con có tổng lớn nhất là [3, -2, 5, 3], với tổng là 9. FullHouse Dev cần phải xác định được dãy con này để đưa ra kết quả chính xác.