O(n)时间求一个数组里具有最大和的连续子集

有一个数组A={a1,a2,...,an}，求一个连续的子段的最大和，即ai,a_i+1, ... a_j-1,aj的和是A中最大的连续子段。

先给个大牛的贪心法：(为什么我觉得更像DP？）
ret=a[0],t=0;
for(i=1; i<n; i++){
    if(t<0) t=0;
    t+=a[i];
    if(t>ret) ret=t;
}
return ret; 

思路是：枚举以i为结尾的最大子段和

另外一个O(n)的算法是：
开另外一个数组s,s[i] = sum( a[0] ... a[i] )
由于s[j] - s[i] = sum (a[i+1] .. a[j] )
因此要maximize这个sum
则必须找一个最大的s[j]与一个最小的s[i]来maximize s[j]-s[i]
一个特例是，最小的s[i]初始为0，因为s[j]-s[i]不能表示到a[0]开始这个范围。
因此最小的s[i]必须为负数，否则必须为0