面试题42. 连续子数组的最大和

[fireairforce]

一个简单的dp,状态转移方程式 f[i] = Math.max(nums[i],f[i-1] + nums[i])

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