直指Offer42.陆续子数组的唯一和

leetcode题目： https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

输入一个整数数组，其中一个或多个连续整数组成一个子数组。求所有子阵列总和的最大值。

所需的时间复杂性为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子阵列 [4,-1,2,1] 最大的，。 6。

动态规划分析：
来源： https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

• 状态定义： 设置动态计划列表 dp ，dp[i] 表示元素。 nums[i] 为结尾的连续子阵列最大和。
• 为什么定义最大值和 dp[i] 元素必须包含在 nums[i] ：保证 dp[i] 递推到 dp[i+1] 正确的；如果不包括 nums[i] ，推送时，不符合主题 连续子阵列 要求。
• 传递方程： 若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负面影响，即。 dp[i−1]+nums[i] 还不如 nums[i] 本身大。
• 当 dp[i - 1] > 0 时：执行 dp[i] = dp[i-1] + nums[i] ；
• 当 dp[i−1]≤0 时：执行 dp[i]=nums[i] ；
• 初始状态： dp[0] = nums[0] ，即以 nums[0] 结尾的连续子阵列最大和为 nums[0] 。

• 返回值： 返回 dp 列表中的最大值，表示全局最大值。

  var maxSubArray = function (nums) { let len = nums.length let pd = [nums[0]] //前面的 连续数组和为负数，贡献为负数。如果是正数，则做出积极贡献是一项持续的任务。 for (let i=0;i<len;i++){ if(pd[i - 1] > 0){ pd[i]=pd[i-1]+nums[i] }else{ pd[i]=nums[i] } } return Math.max(...pd)

  };