Leetcode: Sword Finger offer 42. Somme maximale des sous - tableaux consécutifs

Saisissez un tableau entier,Un ou plusieurs entiers consécutifs d'un tableau forment un sous - Tableau.Trouver la valeur maximale de la somme de tous les sous - tableaux.

La complexité temporelle requise estO(n).

Exemple1:

Entrée: nums = [-2,1,-3,4,-1,2,1,-5,4]
Produits: 6
Explication: Sous - tableaux consécutifs [4,-1,2,1] Et Max.,Pour 6.

Conseils：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100
  Attention!：Ce sujet et la station principale 53 Même question.：https://leetcode-cn.com/problems/maximum-subarray/

---

Comment résoudre le problème

1.Définissez d'aborddpLe tableau représente la plus grande sous - séquence se terminant par l'élément courant et,Et traversernumsLe tableau calcule chaquedpValeur de l'élément,Retourner le maximum à la fin
2.Équation de transfert d'état：dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])

Code

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