leetcode中如何找到最大子序和

發布時間：2022-01-17 11:50:38 來源：億速云閱讀：143 作者：小新欄目：大數據

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

題目鏈接

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

題目描述

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

示例:

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

進階:

如果你已經實現復雜度為 O(n)的解法，嘗試使用更為精妙的分治法求解。

解題方案

思路

標簽：動態規劃
這道題用動態規劃的思路并不難解決，比較難的是后文提出的用分治法求解，但由于其不是最優解法，所以先不列出來
動態規劃的是首先對數組進行遍歷，當前最大連續子序列和為sum，結果為ans
如果sum > 0，則說明sum對結果有增益效果，則sum保留并加上當前遍歷數字
如果sum <= 0，則說明sum對結果無增益效果，需要舍棄，則sum直接更新為當前遍歷數字
每次比較 sum 和 ans的大小，將最大值置為ans，遍歷結束返回結果
時間復雜度：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;
};