leetcode刷题记录（五十六）——53. 最大子数组和

（一）问题描述

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

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

（二）解决思路

 一看到数组中的连续子数组，我又想到滑动窗口了。但NO NO NO，这道题和209.长度最小的子数组还有560. 和为 K 的子数组可一样，它既不能保证元素都为正，子数组的和也不是个确定值，窗口移动的依据无法确定！

这里560. 和为 K 的子数组中有个可以借鉴的思路：前i个元素的状态是由前i-1个元素的状态决定的。如果以第i个元素为结尾的所有子数组的最大和为f(i)，那么f(i)就应该是f(i-1)+nums[i]和nums[i]中的最大值！（注意，这里的f(i)是以第i个元素为结尾，但不一定是从nums[0]开始算哦！）

每个元素的状态是由它上一个元素的状态推导出来的——动态规划！用变量pre来记录以当前元素为结尾的所有子数组和的最大值，再取每个最大值中的最大值，就是最终结果了。

class Solution {
    public int maxSubArray(int[] nums) {


        //找出以每个元素为结尾的最大值

        int pre=0,maxAns=nums[0];

        //递推公式：f(i)=max{f(i-1),f(i-1)+nums[i]}
        for(int i=0;i<nums.length;i++){

            //pre是以当前元素为结尾的所有子数组和的最大值
            //当前的最大值要么等于pre(i-1)+nums[i]要么等于nums[i]
            pre=Math.max(nums[i],pre+nums[i]);

            //比较各个最大值，得到的最终的最大值就是结果
            maxAns=Math.max(maxAns,pre);
        }
        return maxAns;
    }
}

（三）易错点

        递推关系不要搞错啊，是f(i)=max{f(i-1)+nums[i], nums[i]}，可不是 f(i)=max{f(i-1)+nums[i], f(i-1)}呀。想明白是以nums[i]为结尾，但不一定是从nums[0]开始算，就能分清楚啦。

原文地址：https://blog.csdn.net/weixin_45994787/article/details/145169277

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！