题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路1

贪心法。

• 记录当前子序列的和curSum;
• 如果curSum>0，说明curSum对接下来的结果有增益效果，则curSum加上下一个数字；
• 如果curSum<=0，则说明curSum对不会使接下来的结果变大，所以丢弃curSum，从下一个数字重新开始计算curSum;
• 比较curSum与当前子序列和的最大值maxSum，将两者之中的较大者赋给maxSum.
  代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        if(nums.size()==1){
            return nums[0];
        }

        int curSum = 0;
        int maxSum = 0x80000000;
        for(int i=0; i<nums.size(); i++){
            if(curSum<=0){
                curSum = nums[i];
            }else{
                curSum+=nums[i];
            }
            maxSum = max(curSum, maxSum);
        }
        return maxSum;
    }
};

• 时间复杂度：O(n)
  因为只遍历一遍数组，所以时间复杂度为O(n).
• 空间复杂度：O(1)

技巧

可以将0x80000000（int最小值）赋值给max用来记录最大值，0x7fffffff(int最大值)赋值给min用来记录最小值。