【牛客】JZ42 连续子数组的最大和

知识点：动态规划、贪心
链接：JZ42 连续子数组的最大和

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size() == 1)
        {
            return array[0];
        }
        
        int ret = array[0];
        int max = array[0];
        
        /*
        -1 -2 3 2
        -1 -10 -1
        */
        for(size_t i = 1; i < array.size(); ++i)
        {
            ret += array[i];
            //如果a1 + a2 比 a2 还小。没有作用不加，从a2开始加
            if(ret < array[i])
            {
                ret = array[i];
            }
            
            //如果此时的ret 比 max 大，给max
            if(ret > max)
            {
                max = ret;
            }
            
        }
        
        
        return max;
    }
};

最后

以上就是甜美石头为你收集整理的【牛客】JZ42 连续子数组的最大和的全部内容，希望文章能够帮你解决【牛客】JZ42 连续子数组的最大和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。