原题链接

动态规划

遍历数组，以当前遍历到的每一个点为终点来计算当前子序列的最大和，每一个点的结果都是基于前一个点的最大子序列和计算得出的。

状态转移方程

res[i] = Math.max(res[i - 1] + cur[i], cur[i])

• cur: 当前最大连续子序和
• res: 最终结果

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

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

状态压缩

每一个点的结果只和前一个点有关，我们仅用一个变量来维护即可，可以将空间复杂度降低到 O(1)。

对数组进行遍历，如果 cur 大于 0，则 cur 加上当前遍历的数字 num。

否则 cur 只会对当前结果起到负作用，并不是我们想要的，需要舍弃，更新当前遍历数字 num 为 cur。

每次遍历最后需要比较 res 和 cur 的大小，将最大值给到 res。

遍历结束后返回结果。

constmaxSubArray=function(nums){letres=nums[0]letcur=0for(constnumofnums){if(cur>0){cur+=num}else{cur=num}res=Math.max(res,cur)}returnres}

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