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.
最大子序列：
假设某个子序列a[1],a[2],a[3],a[4],....,a[n]为最大子序列，则a1+a2+....+ai>0恒成立，1 <= i <= n
否则可得到a[i+1] + a[i+2] + ....+ a[n] > a[1]+a[2]+....+a[n]，即左边是更大的子序列，与假设矛盾。
因此基于上述结论，从序列第一个元素开始计算sum。
令max表示sum中出现的最大值，同sum相同初始化为序列第一个元素。
若当sum<=0时，则抛弃前面的所有元素，从新一个元素开始计算sum
即如果sum = a[i]+a[i]+1+....+a[j]>0，而a[i] + a[i+1] + a[i+2] +...+a[j] + a[j+1] <= 0时，则令sum 成为一下元素值，即sum = aj+2。
直至遍历一遍完成，时间复杂度为O（n）
具体代码如下
class Solution { public: int maxSubArray(vector<int>& nums) { int sum = nums[0]; int max = sum; for(int i = 1; i < nums.size(); ++i) { if(sum <= 0) { sum = nums[i]; } else{ sum += nums[i]; } max = max > sum ? max : sum; } return max; } };
