leetcode 53.最大子序和

黑暗主宰

于 2019-11-20 09:32:46 发布

阅读量387

点赞数

分类专栏： leetcode刷题文章标签： leetcode53 cpp c++ 最大子序列和

本文链接：https://blog.csdn.net/EngineerHe/article/details/103156314

版权

leetcode刷题专栏收录该内容

127 篇文章

订阅专栏

本文介绍了解决LeetCode第53题——最大子序和的方法，通过动态规划思路，实现了O(n)的时间复杂度。以[-2,1,-3,4,-1,2,1,-5,4]为例，详细阐述了如何找到具有最大和的连续子数组及其最大和。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

leetcode 53.最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路

这一题用python语言很详细的写过，博客链接点这里，附带图文，这里就不重复粘贴了。采用动态规划的思路，时间复杂度为 $O (n)$

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