1. 题目
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
2. 示例
输入: nums = [1,-2,3,10,-4,7,2,-5]
输出: 18
解释: 连续子数组 [3,10,-4,7,2] 的和最大，为 18。
3. 分析
第i位连续子数组的最大和，要看第i-1位连续子数组的最大和对第i位来说有没有增益：
（1）假如第i-1位的连续子数组的最大和为正，那么一定对第i位有增益，连续子数组最大和为第i-1位的连续子数组的最大和+第i位数据
（2）假如第i-1位的连续子数组的最大和为负，那么对第i位没有增益，就舍弃掉第i-1位的连续子数组最大和，只留下第i位数据成为连续子数组最大和
所以，可以提炼一个函数：
Fun(i) = max(Fun(i-1)+a[i-1]，a[i-1])
其中：i代表数组第i位，i-1就是数组下标
（3）得到每一位元素的连续子数组的最大和之后，再从他们中找到最大的那一个
4. 代码实现
1. class Solution { 2. public: 3. int maxSubArray(vector<int>& nums) { 4. vector<int> sum; 5. sum.resize(nums.size()+1);//需要多分配一个空间 6. 7. //计算每一个元素的最大连续子数组和 8. for(size_t i = 1;i<sum.size();i++) 9. { 10. sum[i] = max(sum[i-1]+nums[i-1],nums[i-1]); 11. } 12. 13. //从最大连续子数组和中挑出最大的 14. int max = sum[1];//不赋值sum[0]的原因是，如果nums数组本来全都是负数，那么最大连续子数组和全为负数，而sum[0]本来就是0，如果给max赋初值为sum[0]，那么nums的每个元素的最大连续子数组和都为负数，sum[0]就成了整个数组的最大连续子数组和 15. 16. for(size_t i = 1;i<sum.size();i++) 17. { 18. if(sum[i] > max) 19. { 20. max = sum[i]; 21. } 22. } 23. 24. return max; 25. } 26. };
