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

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let dp = [nums[0]];
  let len = nums.length;

  for (let i = 1; i < len; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
  }

  return Math.max(...dp);
};

var maxSubArray = function (nums) {
  let max = nums[0];
  let pre = max;
  let len = nums.length;
  for (let i = 1; i < len; i++) {
    pre = Math.max(pre + nums[i], nums[i]);
    max = Math.max(max, pre);
  }

  return max;
};

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。

const findLength = (A, B) => {
  const m = A.length;
  const n = B.length;
  const dp = new Array(m + 1);
  for (let i = 0; i <= m; i++) {
    // 初始化整个dp矩阵，每个值为0
    dp[i] = new Array(n + 1).fill(0);
  }
  let res = 0;
  // i=0或j=0的base case，初始化时已经包括
  for (let i = 1; i <= m; i++) {
    // 从1开始遍历
    for (let j = 1; j <= n; j++) {
      // 从1开始遍历
      if (A[i - 1] == B[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } // A[i-1]!=B[j-1]的情况，初始化时已包括了
      res = Math.max(dp[i][j], res);
    }
  }
  return res;
};