刷題92—動态規劃（九） 連續數列

138.連續數列

題目連結

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/contiguous-sequence-lcci

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

題目描述

給定一個整數數組，找出總和最大的連續數列，并傳回總和。

示例：

輸入： [-2,1,-3,4,-1,2,1,-5,4]

輸出： 6

解釋： 連續子數組 [4,-1,2,1] 的和最大，為 6。

進階：

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

題目分析

1. 定義數組dp[i]：以nums[i]結尾的最大的連續數列和；
2. 狀态轉移方程：dp[i] = Math.max(dp[i-1]+nums[i-1],nums[i-1])；
3. 傳回res：res = Math.max(res,dp[i])，res是nums中最大連續子序列和。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let n = nums.length;
    let dp = new Array(n);
    dp[0] = nums[0];
    dp[1] = nums[0];
    let res = dp[1];
    for(let i=2; i<=n; i++){
        dp[i] = Math.max(dp[i-1]+nums[i-1],nums[i-1]);
        res =  Math.max(res,dp[i]);
    }
    return res;
};