最大子数组和（LeetCode 53）

53. 最大子数组和

思路分析：
f(i)表示以 arr[i]结尾的连续子数组的最大和，则可以得到动态转移方程
f(i+1) = Math.max( f(i)+nums[i], nums[i] )
而 f(0) = -2是确定的初始条件
初始解法1：把所有f(i)放到数组里，返回最大值，空间复杂度较高O(n)

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

进阶解法2：在解法1的思想上，用一个变量记录生成过的f(i)的最大值，遍历完了，最大值就出来了，
空间复杂度较低O(1)

var maxSubArray = function(nums) {
  let pre = 0
  let max = nums[0]
  nums.forEach(num => {
    pre = Math.max(pre+num, num)
    max = Math.max(max, pre)
  })
  return max
};