O（N）时间，O（1）空间
连续子数组的最大和
http://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
class Solution: def FindGreatestSumOfSubArray(self, a): s = 0 ret = a[0] for i in a: s = s+i ret = max(s,ret) if s < 0: s = 0 return ret
s表示前i个元素的最大连续和（在必定包括i的条件下，否则为0）
所以，在s=i+s使得s为负时，i过于负贡献时，设置s为0
ret表示前i个元素的最大连续和（可不包括i）。所以最后可直接返回ret。
初始值设置为第一个元素，这样才能保证数组全为负数时，返回一个最大负数。
投递牛客等公司6个岗位 >