[MAXSUB] MAXSUB

Cho một dãy gồm n số nguyên a[1], a[2], ..., a[n]. Hãy tìm một dãy con gồm các phần tử liên tiếp (có ít nhất một phần tử) sao cho tổng các phần tử của nó là lớn nhất, và in ra tổng đó.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên n (1 ≤ n ≤ 1000).
• Dòng thứ hai chứa n số nguyên a[i] (|a[i]| ≤ 10^9), cách nhau bởi dấu cách.

Kết quả

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

Ghi chú

• Tổng có thể lớn hơn phạm vi số nguyên 32-bit, hãy dùng kiểu 64-bit (long long trong C++; Python tự xử lý).
• Dãy con không được rỗng. Nếu mọi số đều âm thì đáp án là số âm lớn nhất trong dãy.