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 FORMAT

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 FORMAT

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

Ví dụ 1:

Input

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

Ouput

9

Giải thích ví dụ mẫu:

• 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.
    Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House