leetcode-最大子序和

本文主要是介绍leetcode-最大子序和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

https://leetcode-cn.com/problems/maximum-subarray/

思路

1. dp
2. 贪心

code

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    // return greedy(nums);
    return dp_f(nums);


};

const greedy = function (nums) {
    let max = -Infinity;
    let cur = 0;
    let len = nums.length;
    for (let i = 0; i < len; i++) {
        cur += nums[i];
        if (cur > max) max = cur;
        if (cur < 0) cur = 0;
    }
    return max;
}

const dp_f = function (nums) {
    let dp = 0;
    let res = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        dp = Math.max(nums[i] + dp, nums[i]);
        res = Math.max(res, dp);
    }

    return res;
}

这篇关于leetcode-最大子序和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！