Tổng mảng con lớn nhất

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Cho một mảng có \(N (1 \leq N \leq 10^6)\) phần tử bạn cần tìm tổng lớn nhất của một mảng con liên tiếp không rỗng.

Input

Dòng đầu tiên chứa số nguyên \(N\) ( \(N \leq 10^6\)).

Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, a_3, .... a_n\), mỗi số các nhau một dấu cách \((|a_i| < 10^{9})\)

Output

In ra tổng lớn nhất của một mảng con không rỗng.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

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

Output

9

Giải thích ví dụ

• Ví dụ 1:
  • Tổng lớn nhất của một mảng con liên tiếp là 9, tính từ các phần tử 5 3 -5 2 2.

Thông tin học tập

• Buổi: B10
• Concepts: 1D arrays, one-state DP, Kadane algorithm
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 25