即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCode 53. Maximum Subarray

编程语言 helloiamclh 21℃ 0评论
本文目录
[隐藏]

1.题意

求一个序列中最大的子序列和

2.思路

很经典的题目了,可以DP,很麻烦的线段树也可以实现,这里使用一个巧妙的方法,代码很短,手动模拟一下即可理解.

3.代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        size_t len = nums.size();
        int ans = INT_MIN;
        int sum = 0;
        for(int i = 0; i < len; i++){
            sum += nums[i];
            ans = max(ans, sum);
            if(sum < 0){
                sum = 0;
            }
        }
        return ans;
    }
};

转载请注明:CodingBlog » LeetCode 53. Maximum Subarray

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情