题目：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
思路：
本题要求出给定数组中由若干相邻元素组成的子数组的最大和。
想要使算法的时间复杂度为O(n)，则必须承认下述事实：
假设数组N中从第i到第j这些元素组成的子数组N[i.......j]和为最大，则对于p(i<=p<j)来说，子数组N[i......p]的和必须大于0。否则N[i......j]的和不是最大和，最大和对应的子数组应该为N[p+1......j]。
从第一个元素开始向后累加，和为sum，对于元素N[k]，如果N[k] > N[k]+sum，则表明sum<0，对最大和结果的增长起反作用，要将其丢弃，sum的结果重新定位为N[k]的值。否则，sum对最大和结果起正作用，sum的结果为sum+N[K]。
以上步骤每运算一次，将sum值与最大和maxsum进行比较取最大。遍历一遍即可得到最终结果。
为了避免数组内全为负数的情况，将sum与maxsum的初始值都定义为一个小的负数-99999
代码：
python实现
class Solution(object): def maxSubArray(self, nums): if len(nums) == 1: return nums[0] sum = -99999 maxsum = -99999 for i in nums: if i > sum + i: sum = i else: sum = sum + i maxsum = max(maxsum, sum) return maxsum
