Maximum Subarray Problem

You are given a sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$. Find the maximum value of

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$

For each case, print the maximum value on its own line.

• $1\leq T\leq100\,000$.
• $1\leq N\leq10^6$.
• $-10^9\leq A_i\leq10^9$ ($1\leq i\leq N$).
• The sum of $N$ over all cases is at most $10^6$.