一、题目内容 简单
给你一个整数数组 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
二、解题思路
贪心的思路就是:一直取局部最优,以获得全局最优。
局部最优:就是当前“连续和”为负数的时候,立刻放弃,从下一个元素重新计算“连续和”,因为负数会拉低往后的“连续和”。
全局最优:取最大的“连续和”。
从代码的角度上将,遍历 nums,令“连续和”为 curNum,“最大连续和”为 maxNum。
当连续和为负数,即 curNum < 0 时,curNum + nums[i] < nums[i]
可将 curNum = Math.max(curNum + nums[i], nums[i])
,使得 curNum 从下一个元素重新计算。maxNum = Math.max(curNum, maxNum)
,比较当前连续和 与 最大连续和大小,取最大。
三、具体代码
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let curNum = maxNum = nums[0];
for (let i = 1;i < nums.length; i++) {
curNum = Math.max(curNum + nums[i], nums[i]);
maxNum = Math.max(maxNum, curNum);
}
return maxNum;
};
/**
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
四、其他解法
动态规划
我们利用上面贪心的核心思想,遇到“数组和”为负,则从下一个元素开始重新计算。
当数组元素为 1 时,直接返回
当数组元素为 2 时,nums[1] = Math.max(nums[1], nums[1] + nums[0])
,然后排序 nums,返回最大值
当数组元素为 3 时,nums[1]
如上面所说计算得出,nums[2] = Math.max(nums[2], nums[2] + nums[1])
当数组元素为 n 时,同理依次类推,nums[i] = Math.max(nums[i], nums[i] + nums[i - 1])
,然后对 nums 进行排序,取最大值。
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
for(let i = 1;i < nums.length;i++) {
nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
}
nums.sort((a, b)=> b - a);
return nums[0];
};