1077最大序列和

给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。
对于S的所有非空连续子序列T，求最大的序列和。
变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。

输入：

第一行为一个正整数N，第二行为N个整数，表示序列中的数。

输出：

输入可能包括多组数据，对于每一组输入数据，
仅输出一个数，表示最大序和

本题首先要想到要用 long long int 来表示最大序列和，另外还要注意一点就是输入的n个数，同样也要用long int 表示，不然也会越界。看到这题有很多方法，相对来说动态规划是比较简洁的。

下面列出推出其状态转移方程的过程。

a[i]是输入的原始数列元素，sum[i]是从a[1]~a[i]之间包含a[i]的最大子段和，将sum[i]都求出来后，最最大值即为所求。（sum[]要用long long int)

假设sum[i-1]已经求出，那么要求sum[i],就要看sum[i-1]加上a[i]和a[i]哪个大 即sum[i]=max(sum[i-1]+a[i],a[i]) 这里有点要理解的地方，因为题目中要求的是连续子序列，所以sum[i]=max(sum[i-1]+a[i],a[i])而不是 sum[i]=max(sum[i-1]+a[i],sum[i-1]),因为如果是后面的式子的话其求的的子序列不是连续的，这就不符合题目要求。

下面就可以写出计算sum[i]的伪码

sum[0]= a[0]; intmaxSum = sum[0]; for(inti = 1; i < n; i++) { sum[i]= max(sum[i - 1] + a[i], a[i]); maxSum= max(maxSum, sum[i]); } 最终maxSum 保存的就是sum[i]中的最大值。