题目：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
初次拿到这个题目，最直接的想法是：遍历整个数组，求其所有的子序列，然后找最大的。其大致思路自然是用两个索引i,j，然后获取i,j之间的数组的值，然后用打擂台法获取最大的；这种方法的时间复杂度是o（n^2）。
有没有更好的办法？或者说我们能不能找到一种策略，使得下一次的结果一定比上次大，这样我们只需要遍历一次数组就可以？
当然有，这种思想就是：如果当前序列和为负数，那么下一个寻找开始的位置。就不再包含当前位置及以前位置的数，！
我们借助这个思想分析一下上述示例数组：[-2,1,-3,4,-1,2,1,-5,4],
1 第一次：当前序列和sum = -2<0;因此不再考虑位置0的数 2 第二次：当前序列和sum = 1 >0;则当前最大和max_sum = 1；考虑位置1的数 3 第三次：当前序列和sum = 1+-3 = -2<0；因此不再考虑-3以前的数； 4 第四次：当前序列和sum = 4>0;则当前最大和sum_max = 4;此时最大序列为4； 5 第五次：当前序列和sum = 4+-1=3>0；则当前最大和sum_max = 4;此时最大序列为4；但由于sum>0，我们仍然需要考虑将4作为起始点 6 第六次：当前序列和sum = 4+-1+2 = 5>0;当前最大序列和sum_max = 5;此时最大序列[4,-1,2]; 7 第七次：当前序列和sum = 4+-1+2+1 = 6>0；当前最大序列和sum_max = 6；此时最大序列[4,-1,2,1]； 8 第八次:当前序列和sum = 4+-1+2+1 +-5 = 1>0；sum_max = 6；此时最大序列[4,-1,2,1]； 9 第九次：当前序列和sum = 4+-1+2+1 +-5+4 = 5>0；sum_max = 6,此时最大序列为 10 [4,-1,2,1]； 11 结束！
就这样，当我们遍历完数组的时候，最大子序列就找到了；可见时间复杂度是O(n)；
在这里有人也许会问：上述只是从位置3的元素4遍历到了结尾。会不会存在从位置3后面开始，到某个位置的数比从元素4开始的序列[4,-1,2,1]序列和更大？
显然不会，为何？因为我们说过，只要当前序列和<0，我们就舍弃之前所有的位置；而序列和>0，我们就保留那些位置。因此，我们保留了从4开始的位置。说明了序列和是大于0的；而从4后面开始，显然是从4开始的序列的子集，其和不可能大于从4开始。
那么上述思路有一个明显的漏洞是：如果当前序列和为负数，从下一个位置开始，不再包含当期所有位置；显然如果数组所有元素都是负数。那么我们最终是找不到一个最大和子序列的；但是我们知道如果一个序列全是负数，最大子序列就是其中最大的负数，因此，我们应该单独考虑全为负数的情况。
那么我们怎么考虑一个数组全部为负数呢？很简单，如果一个数组的最大元素为负数，那么整个数组就为负数。因此，我们可以给出完整的求最大子序列的代码：
1 class Solution { 2 public: 3 int maxSubArray(vector<int>& nums) { 4 int max = 0,temp = 0; 5 int allnegative_max = nums[0]; 6 for (int i = 0; i < nums.size(); i++) { 7 temp += nums[i]; 8 if (temp < 0) 9 temp = 0; 10 if (max < temp) 11 max = temp; 12 if(nums[i] > allnegative_max) 13 allnegative_max = nums[i];//用于判断是否全部为负数 14 } 15 if(allnegative_max < 0)//说明数组全部为负数 16 return allnegative_max; 17 else 18 return max; 19 } 20 };
当然了，这个题目可以进一步的提问：找到最大和子序列的起始位置？那么又该如何编码呢？
class Solution { public: int maxSubArray(vector<int>& nums) { int max = 0,temp = 0; int start1,start2; int allnegative_max = nums[0]; for (int i = 0; i < nums.size(); i++) { temp += nums[i]; if (temp < 0) { temp = 0; start1 = i+1; } if (max < temp) max = temp; if(nums[i] > allnegative_max) { allnegative_max = nums[i];//用于判断是否全部为负数 start2 = i; } } if(allnegative_max < 0)//说明数组全部为负数 return allnegative_max; else return max; } };
其中start1和start2表明了位置