求解最大子序和应该怎么做？？｜刷题打卡

今天的题目是这个53. 最大子序和

一、先看题

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

示例1：

示例2：

示例3：

示例4：

示例5：

提示：

• 1<=nums.length<=3∗104
• −105<=nums[i]<=105

原题链接：53. 最大子序和

二、整理思路

初步看来，题目不难，甚至可以说是简洁。先对题目分析一番。

首先看关键字：最大和、连续子数组

既然是连续子数组，那么前一个子数组的和必然会影响到下一个元素，因此我们可以考虑使用动态规划算法的思想进行解答。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let res = nums[0];
    for(let i=1;i<nums.length;i++){
        //以max替代了if更简洁
        nums[i] += Math.max(nums[i-1],0)
        res = Math.max(res,nums[i])
    }
    return res
};

在这道题中，最难的一部分应该就是对转移方程的定义，借用leetcode K神的一张图解释就是：

当前一个子数组的和比0还小的时候，那么不是越加越少了吗？这种时候还不如直接用新的元素替代掉，成为一个新的开始。

当时自己思考的时候，就是这里没有想清楚，一直拿前一个元素和当前元素对比，这样子比较是没有用的，因为其实它前面那一系列元素都会影响到加入当前元素后的和。

因此要将和进行比较才是正确思路。

原题题解：53. 最大子序和

三、总结

以动态规划思想求解，一般来说最重要的就是理清思路，找到题目对应的转移方程，然后根据转移方程进行编程求解。

如果遇到前面的元素会影响到后面元素抉择的场景，就应该立刻想到动态规划的思想，这样更有效率。

一起加油吧！

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情