leetcode中如何找到最大子序和

發(fā)布時(shí)間：2022-01-17 11:50:38 來源：億速云閱讀：135 作者：小新欄目：大數(shù)據(jù)

小編給大家分享一下leetcode中如何找到最大子序和，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

題目鏈接

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

題目描述

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n)的解法，嘗試使用更為精妙的分治法求解。

解題方案

思路

標(biāo)簽：動(dòng)態(tài)規(guī)劃
這道題用動(dòng)態(tài)規(guī)劃的思路并不難解決，比較難的是后文提出的用分治法求解，但由于其不是最優(yōu)解法，所以先不列出來
動(dòng)態(tài)規(guī)劃的是首先對(duì)數(shù)組進(jìn)行遍歷，當(dāng)前最大連續(xù)子序列和為sum，結(jié)果為ans
如果sum > 0，則說明sum對(duì)結(jié)果有增益效果，則sum保留并加上當(dāng)前遍歷數(shù)字
如果sum <= 0，則說明sum對(duì)結(jié)果無增益效果，需要舍棄，則sum直接更新為當(dāng)前遍歷數(shù)字
每次比較 sum 和 ans的大小，將最大值置為ans，遍歷結(jié)束返回結(jié)果
時(shí)間復(fù)雜度：O(n)

代碼

Java版本

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

JavaScript版本

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let ans = nums[0];
    let sum = 0;
    for(const num of nums) {
        if(sum > 0) {
            sum += num;
        } else {
            sum = num;
        }
        ans = Math.max(ans, sum);
    }
    return ans;
};