Hãy tìm một đoạn trong mảng có trọng số lớn nhất, nghĩa là tổng các số trong đoạn là lớn nhất.

• Cho mảng s = (a₁, . . . , a_n) 
• một đoạn s(i, j) = (a_i , . . . , a_j) , 1 ≤ i ≤ j ≤ n
• trọng số w(s(i, j)) = a_i + a_i+1 . . . + a_j

Yêu cầu: Hãy tìm một đoạn trong mảng có trọng số lớn nhất

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên n ≤ 10⁶ .
• Dòng thứ hai chứa n số nguyên.

Kết quả

Ghi ra duy nhất một số nguyên là trọng số lớn nhất tìm được.