53、最大子数组和

;(function () {
  /**
   * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
   * 子数组 是数组中的一个连续部分。
   * @param {number[]} nums
   * @return {number}
   */
  var maxSubArray = function (nums: number[]) {
    let pre = 0
    let maxNum = nums[0]
    nums.forEach((x) => {
      pre = Math.max(pre + x, x)
      maxNum = Math.max(maxNum, pre)
    })
    return maxNum
  }
  console.log(maxSubArray([1, 2, -3, 4, 1, 4, 5, -2, 3, -5, 8]))

  // 衍生：如何获取最大子数组？
  /**
   * @param {number[]} nums
   * @return {number}
   */
  var maxSubArrayGet = function (nums: number[]): number[] {
    let pre = 0
    let maxNum = nums[0]
    let maxArr: number[] = []
    nums.forEach((x) => {
      // 【A: 累加的值(pre + x)】与 【B: 现在遍历的值(x)】 对比
      pre = Math.max(pre + x, x)
      maxNum = Math.max(maxNum, pre)
      // A === B，maxArr重置，否则push B
      pre === x ? (maxArr = [x]) : maxArr.push(x)
    })
    return maxArr
  }
  console.log(maxSubArrayGet([1, 2, -3, 4, 1, 4, 5, -2, 3, -5, 8]))
})()