力扣-- 最大子数组和

65 阅读 0 评论 43 点赞

我是靠谱客的博主爱笑百褶裙，最近开发中收集的这篇文章主要介绍力扣-- 最大子数组和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最大子数组和

题目:
给你一个整数数组 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

C

思路：

贪心算法：局部最优解
max存放当前求和最大值，sum存放求和值，遍历数组，如果sum求和值小于0，直接丢弃当前元素到下一个元素，如果求和值大于max，重新给max赋值为sum

代码:

int maxSubArray(int* nums, int numsSize){
    //贪心算法
    //局部最优解
    //1.遍历数组
    //2.max sum 如果sum大于0保留 sum<0丢弃
    int i;
    //初始化sum和为0
    int sum = 0;
    //初始化max为最小
    int max = INT_MIN;
    for(i=0; i<numsSize; i++){
        sum += nums[i];
        if(sum > max){
            //如果sum和大于max 重新赋值max
            max = sum;
        }
        if(sum < 0){
            //如果sum值小于0 丢弃
            sum = 0;
        }
    }
    return max;
}

JS

思路

如上一样
注意：js中数值的最小用 -Number.MAX_VALUE表示

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    //初始化max
    let max = -Number.MAX_VALUE
    //初始化sum
    let sum = 0
    //遍历
    nums.forEach((items) => {
        sum += items
        if(sum > max){
            max = sum
        }
        if(sum < 0){
            sum = 0
        }
    })
    return max
};