题目描述

给一串整数$\red {a[1],a[2]…a[n]}$，求出它的最大的子序列和，即找出$\red {1<=i<=j<＝n}$，使得$\red {a[i]+a[i+1]+…+a[j]}$的和最大。

输入格式

共两行，第一行为一个数字，表示有$\red N$个整数，$\red {N<=35000}$。第二行为$\red N$个整数，以空格分隔。

输出格式

共一行，即最大的子序列和。

样例

输入样例

5

1 2 5 －10 7

输出样例

8

提示

方法一：纯枚举$\red {O(n^3)}$

方法二：前缀和$\red{O(n^2)}$

方法三：从最后一个数据开始倒数相加(与$\red b$相加，$\red b$的初值为$\red 0$)，然后每一次相加后与最大值比较，如果大于最大值就替代它；如果相加出现小于$\red 0$的情况，与最大值比较后，把$\red b$清零；重复了上步骤，最后即可求出最大值。