☆打卡算法☆LeetCode 53、最大子序和 算法解析

一、题目

1、算法题目

“给定一个整数数组，找到最大和的连续子数组，返回其最大和。”

题目链接：

来源：力扣（LeetCode）

链接：53. 最大子序和 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

二、解题

1、思路分析

这个题解法很多，可以使用暴力法、动态规划、贪心法、分治法。

这里就用动态规划法来解这道题。

假设数组的长度是n，下标是0到n-1，f(i)代表连续子数组的最大和，那么只需要求出每个位置的f(i)，不就找到最大和了吗？

那么怎么求每个位置的f(i)呢？这取决于nums[i]和f[i-1]+nums[i]谁更大，所以就可以推到出动态规划转移方程：

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

2、代码实现

代码参考：

public class Solution {
    public int MaxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        foreach (int x in nums) {
            pre = Math.Max(pre + x, x);
            maxAns = Math.Max(maxAns, pre);
        }
        return maxAns;
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

我觉得这道题目的思想是：

走完这一生

如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。

我回顾我最光辉的时刻

就是和不同人在一起，变得更好的最长连续时刻