原题链接

状态定义

dp[i]：表示以 nums[i] 为结尾的连续子数组最大和。

状态转移方程

连续子数组则必须包含 nums[i]，否则不符合题意。

当dp[i - 1] > 0 时，dp[i] = dp[i - 1] + nums[i]，当dp[i - 1] <= 0 时，dp[i] = nums[i]。

所以状态转移方程为：

dp[i] = max(dp[i - 1] + nums[i], nums[i])

初始化

dp[0] = nums[0]，以 nums[0] 为结尾的连续子数组最大和为 nums[0]。

我们只需要关注前一个状态的值，不需要额外开辟一个数组空间记录，仅用两个变量即可。

constmaxSubArray=function(nums){constlen=nums.lengthletres=nums[0]for(leti=1;i<len;i++){nums[i]=Math.max(0,nums[i-1])+nums[i]if(nums[i]>res){res=nums[i]}}returnres}

• 时间复杂度: O(n)
• 空间复杂度: O(1)