[数据结构与算法]??LeetCode 最大连续子序列，Maximum Subarray??

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏：LeetCode面试必备100题?（优质好文持续更新中……）🚀

目录

一、题目描述

二、题目样例

三、算法思想

四、代码实现

五、复杂度分析

六、题目链接

一、题目描述

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

其中：

1 <= nums.length <= 3 * 104

-10^5 <= nums[i] <= 10^5

二、题目样例

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

说明：在数组 nums 中，连续子序列 [4, -1, 2, 1] 的和是所有连续子序列中最大的，故连续子序列的和最大为 6 。

三、算法思想

这是一道非常经典的题目，是一道非常基础的动态规划题目，假设 dp[i] 为以第 i 个元素为结尾的连续序列的最大和，那么，有如下动态转移方程：

dp[i] = max(dp[i-1] + nums[i], nums[i])

上述方程代表以第 i 个元素为结尾的连续序列的最大和等于：以第 i-1 个元素为结尾的连续序列的最大和加上第 i 个元素值和第 i 个元素值的最大值。

因为本题中仅仅是求一个最大值，故可以把转移方程改为：sum = max(sum + nums[i], nums[i])。

四、代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0; // 记录连续子序列的和
        int ans = nums[0]; // 假设最大值为 nums[0]
        for(int i = 0; i < (int)nums.size(); ++i) {
            sum = max(sum + nums[i], nums[i]); // 计算 sum
            ans = max(sum, ans); // 求最大值
        }
        return ans;
    }
};

五、复杂度分析

时间复杂度：O(n)，因为程序整个执行过程只遍历了一次 nums 数组，故时间复杂度为 O(n)；

空间复杂度：O(1)，在程序中，仅用到了 sum 和 ans 两个额外的变量，可以忽略，故空间复杂度为 O(1)；

六、题目链接

力扣

🎈 欢迎小伙伴们点赞👍、收藏?、留言💬

? ? ? ? 欢迎关注下方👇👇👇公众号👇👇👇，获取更多优质内容🤞（比心）！