最大子数组和

Question

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

输入： nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

动态规划

function getMaxSumOfSubArray(arr) {
  // 储存 arr[i] 的尾的连续子数组的和
  const dp = [];
  dp[0] = arr[0];
  let max = dp[0];
  for (let i = 1; i < arr.length; i++) {
    // 如果dp[i - 1] + arr[i] 大，则累加，否则从当前索引重新开始
    dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
    max = Math.max(max, dp[i]);
  }
  return max;
}

console.log(getMaxSumOfSubArray([-2,1,-3,4,-1,2,1,-5,4]))

暴力解法

function getMaxSumOfSubArray(arr) {
  let sum = arr[0];
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length + 1; j++) {
      const subArray = arr.slice(i, j);
      sum = Math.max(
        sum,
        subArray.reduce((acc, cur) => acc + cur)
      );
    }
  }
  return sum;
}

时间复杂度： O(n^3)