53. 最大子序和

题目

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路

1. 首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 res
2. 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
3. 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
4. 每次比较 sum 和 res的大小，将最大值置为res，遍历结束返回结果

时间复杂度：O(n)

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int res = nums[0];
        for(int num:nums){
            if(sum>0){
                sum += num;
            }else{
                sum = num;
            }
            res = max(sum,res);
        }
        return res;
    }
};