LeetCode 53. 最大子序和

文章目录

• 前言
• 题目
• 题解
• NO1：贪心
• NO2：动态规划
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：53. 最大子序和，难度：简单。

题目描述(摘自leetcode)：

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

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

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [0]
输出：0

示例 4：
输入：nums = [-1]
输出：-1

示例 5：
输入：nums = [-100000]
输出：-100000
 
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

---

题解

NO1：贪心

思路：

[-2,1,-3,4,-1,2,1,-5,4]
ans来表示最大值，sum用于临时存储连续子数组的和。
遍历一遍
1、如果sum>0，表示仍有增益，那么直接加上下面的元素。
2、如果sum<=0，那么无论后面的值为正数或小数，前面的其实都无效，此时直接sum=新值即可。
3、每遍历一个元素要与实际存储最大值的res进行比较来取出最大值赋值给res。

代码：时间复杂度O(n)，空间复杂度O(1)

public int maxSubArray(int[] nums) {
    if(nums == null){
        return 0;
    }
    int ans = nums[0];
    int sum = 0;
    for (int i = 0; i < nums.length; i++){
        //若是结果>0，那么直接加上新的元素
        if ( sum > 0 ){
            sum += nums[i];
        }else{ //若是结果<=0，此时前面的的连续子数组不统一,直接设置新的值
            sum = nums[i];
        }
        //此时再将最新组合的数据与原本保留的最大值来进行比较
        ans = Math.max( sum , ans);
    }
    return ans;
}

---

NO2：动态规划

思路：

连续子数组的最大和，以i下标的数与之前i-1个数相比较，通过对nums[i] 和 f(i-1)+nums[i]的大小，来获取一个较大的数。若是前者大说明f(i-1)整和是负数那么直接从nums[i]重新开始，若是后者大表明连续的子数组和为最大即可与后面相连。

f(i)=max{f(i−1)+nums[i],nums[i]}

代码：时间复杂度O(n)，空间复杂度O(1)

public int maxSubArray(int[] nums) {
    if (nums.length == 1){
        return nums[0];
    }
    int pre = nums[0], maxAns = nums[0];
    for (int i = 1; i < nums.length; i++){
        //动规式子：将前面连续的值记上nums[i]与nums[i]进行比较
        pre = Math.max(pre + nums[i], nums[i]);
        maxAns = Math.max(pre, maxAns);
    }
    return maxAns;
}

---

参考文章

[1]. leetcode官方题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.11