최대 부분 배열 문제

길이 $N$의 수열 $A=[A_1,A_2,\cdots,A_N]$이 주어진다. 다음 값의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 케이스마다 최댓값을 한 줄에 출력한다.

• $1\leq T\leq100\,000$.
• $1\leq N\leq10^6$.
• $-10^9\leq A_i\leq10^9$ ($1\leq i\leq N$).
• 모든 케이스에 대한 $N$의 합은 $10^6$ 이하이다.