LeetCode49-最大子序和 | 算法练习系列

这是我参与8月更文挑战的第23天，活动详情查看：8月更文挑战

前言

今天来一道处理数组的算法题，求数组中的最大子序和，何为最大子序和，也就是数组中各个子数组的和的最大值，这是我们可以把子数组一一列举出来进行比较，但明显这样太复杂，不可取，下面分享一个讨巧的方法

题目描述

给定一个整数数组 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

解题思路

• 声明一个数组maxAnd，用来存放循环nums得到的项，声明maxNum用来存放最大值，声明一个andArr用来存放maxAnd数组中各项相加的和
• 具体思路就是，当maxAnd中的数组各项和小于0的时候就舍弃，置空数组maxAnd，当maxAnd的各项和相加大于0是时就push进nums[i]
• 不论是进行数组置空操作还是push操作，都要记得更新最大值maxNum的值，同时也要更新数组maxAnd中各项和的值，也就是andArr
• 还有一点就是在比较的过程中要考虑都是负数的情况，下面上代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxAnd = [nums[0]]
    let maxNum = nums[0]
    let andArr = nums[0]
    for(let i=1;i<nums.length;i++){
        if(andArr>0){
            maxAnd.push(nums[i])
            maxNum=(andArr+nums[i])>maxNum?andArr+nums[i]:maxNum //当maxAnd各项和大于0的情况，更新最大值maxNum，这里用的三目运算符，用if-else也行，这样代码看着更简洁
            andArr = andArr+nums[i]
        }else{
            if(maxAnd.length){
                maxAnd.splice(0,maxAnd.length,nums[i]) //这是maxAnd各项和小于0的情况，置空数组并把nums[i]插入新数组
                if(maxNum<nums[i]){//这里是判断连续输入负数的情况，只有当nums[i]大于最大值时才更新最大值
                    maxNum=nums[i]
                }
                andArr=nums[i]
            }
       }
    }
    return maxNum
};
复制代码

总结

本题大致的思路就是把nums中循环出来的值根据不同情况看是否要插入新数组，每一步更新最大值，最终输出最大值即可。