최대 부분 배열 문제

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

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

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

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

• $1\leq T\leq100\,000$.
• $1\leq N\leq10^6$.