Cho một mảng$\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;"> N </font><font\; dir="auto"\; style="background-color:\; transparent;\; font-family:\; "\; helvetica=""\; neue",=""\; helvetica,=""\; arial,=""\; sans-serif;=""\; vertical-align:=""\; inherit;"="">số\; nguyên,\; nhiệm\; vụ\; của\; bạn\; là\; tìm\; tổng\; giá\; trị\; lớn\; nhất\; trong\; một\; mảng\; con\; liền\; kề,\; không\; rỗng.</font></font>}$

Đầu vào

Dòng đầu vào đầu tiên có một số nguyên$\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;"> N</font><font\; dir="auto"\; style="background-color:\; transparent;\; font-family:\; "\; helvetica=""\; neue",=""\; helvetica,=""\; arial,=""\; sans-serif;=""\; font-size:=""\; 14px;=""\; vertical-align:=""\; inherit;"="">:\; kích\; thước\; của\; mảng.</font></font>}$

Dòng thứ hai có$N$số nguyên${\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">x</font></font>}}_{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">1</font></font>}}<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">,</font></font>{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">x</font></font>}}_{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">2</font></font>}}<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">,</font></font><font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">\dots </font></font><font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">,</font></font>{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">x</font></font>}}_{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">N</font><span\; class="math\; math-inline"\; style="background-color:\; transparent;\; font-family:\; "\; helvetica=""\; neue",=""\; helvetica,=""\; arial,=""\; sans-serif;=""\; font-size:=""\; 14px;"=""><span\; class="katex"><span\; class="katex-html"\; aria-hidden="true"><span\; class="base"><span\; class="mord"><span\; class="msupsub"><span\; class="vlist-t\; vlist-t2"><span\; class="vlist-r"><span\; class="vlist-s"><font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;"></font></font></span></span><span\; class="vlist-r"><span\; class="vlist"\; style="height:\; 0.15em;"><span\; class=""></span></span></span></span></span></span></span></span></span></span><font\; dir="auto"\; style="background-color:\; transparent;\; font-family:\; "\; helvetica=""\; neue",=""\; helvetica,=""\; arial,=""\; sans-serif;=""\; font-size:=""\; 14px;=""\; vertical-align:=""\; inherit;"="">:\; các\; giá\; trị\; mảng.</font></font>}}$

Đầu ra

In ra một số nguyên: tổng mảng con lớn nhất.

Hạn chế

• $1 \le n \le 2 \cdot 10^5$
  
• $<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">-</font></font>\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">1</font></font>}{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">0</font></font>}}^{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">9</font></font>}}<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">\le </font></font>{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">x</font></font>}}_{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;">i</font>}}<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">\le </font></font>\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">1</font></font>}{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">0</font></font>}}^{\mathrm{<font\; dir="auto"\; style="vertical-align:\; inherit;"><font\; dir="auto"\; style="vertical-align:\; inherit;">9</font></font>}}$

Ví dụ

Đầu vào:

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

Đầu ra:

9