题解 | #连续最大和#

该题目为力扣剑指Offer42 连续子数组的最大和 采用动态规划的方法。

我们用dp[i]表示第i个数结尾的连续子数组的最大和。有两种情况，第一种是将arr[i]加入到dp[i-1]的数组中去（此时要求dp[i - 1] > 0）；第二种情况是arr[i]成为连续子数组的初始位置（dp[i-1] <= 0 ）

因此转移方程为 dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])

let n = parseInt(readline());
let arr = readline().split(' ').map(Number);

function maxSum(arr){
   let dp = [arr[0]], max = arr[0];
   for(let i = 0; i < arr.length; i++){
       if(dp[i - 1] > 0){
           dp[i] = dp[i - 1] + arr[i];
       }else{
           dp[i] = arr[i];
       }
       max = Math.max(max, dp[i]);
   }
    return max;
}
console.log(maxSum(arr));

更简单的写法：

let n = parseInt(readline());
let arr = readline().split(' ').map(Number);

function maxSum(arr){
   let dp = [arr[0]];
   for(let i = 1; i < arr.length; i++){
       dp[i] = Math.max(arr[i], dp[i - 1] + arr [i]);
   }
    return Math.max(...dp);
}
console.log(maxSum(arr));