发表文章

[最新] 30. 连续子数组的最大和

weixin39605679 3月前 91

题目:输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。

思路:时间复杂度为O(n)的解法:

遍历数组,保存两个值,一个当前和,一个最大和,  每遍历一个数字,就加在当前和上,如果当前和大于最大和,那么将当前和赋给最大和,如果当前和越来越小,则最大和不变,如果当前和小于0,那么就要开始重新对当前和赋值0,接着再判断是否大于最大和。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size() == 0)
            return 0;
        int cur = array[0];
        int sum = cur;
        for(int i = 1; i < array.size(); ++ i)
        {
            if(cur < 0)
                cur = 0;
            cur = cur + array[i];
            if(cur > sum)
                sum = cur;
        }
        return sum;
    }
};

相关推荐
最新评论 (0)
返回
发表文章
weixin39605679
文章数
55
评论数
0
注册排名
1305258