LeetCode53. 最大子序和

题目

分析

直接暴力，枚举每个起始点的最大和

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        for(int i = 0;i < nums.size();i++){
            int count = 0;
            for(int j = i ;j <nums.size();j++){
                count += nums[j];
                res = max(count,res);
            }
        }
        return res;
        
    }
};

分析（贪心）

贪心要考虑局部最优。res = res + cur ,如果之前计算的总和为负数，那加上当前元素一定会比当前元素小。当前元素为正数，res < cur ,当前元素为负数，依旧 res < cur 。所以如果之前计算总和为负数，它的作用只会降低总和。故当前和为负数，直接从下一个元素开始就好了。并且要实时存放连续子序列和的最大值。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int count = 0;
        for(int i = 0;i < nums.size();i++){
            count += nums[i];
            if(count > res) res = count;
            if(count < 0)  count= 0;
        }
        return res;
        
    }
};

分析（dp）

代码