Dãy con có tổng lớn nhất

Dòng đầu là $n$ ($1 \le n \le 2 \cdot 10^5$). Dòng thứ hai gồm $n$ số nguyên $a_i$ ($|a_i| \le 10^9$).

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

Lời giải $O(n^2)$ chỉ qua được các test nhỏ. Hãy nghĩ cách dùng thuật toán Kadane $O(n)$.