题解 | #72.连续子数组的最大和#

$dp[i]dp[i]$表示以i作为结束的子数组最大和

$dp[i]=max(array[i],dp[i-1]+array[i])dp[i]\; =\; max(array[i],dp[i-1]+array[i])$

含义：要么只选择$array[i]array[i]$一个元素，要么选择$dp[i-1]dp[i-1]$选择的加上$array[i]array[i]$

function FindGreatestSumOfSubArray(array)
{
  let dp = new Array(array.length);
  dp[0] = array[0];
  //dp[i]表示以i作为结束的子数组最大和
  //dp[i] = Math.max(array[i],dp[i-1]+array[i])
  //含义：要么只选择array[i]一个元素，要么选择dp[i-1]选择的加上array[i]
  for(let i=1; i<array.length; i++){
    dp[i] = Math.max(array[i],dp[i-1]+array[i]);
  }
  
  return Math.max(...dp);
}