leetcode 53. 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

题目

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

示例

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

解一：动态规划

思路：

用 $f(i)$ 代表以第 i 个数结尾的「连续子数组的最大和」，问题可以转换为：
$$\max_{0 \leq i \leq n-1} { f(i) }$$
我们只需要求出每个位置的 $f(i)$，然后返回最大值即可。

如何求 $f(i)$ ：
考虑 $nums[i]$ 单独成为一段还是加入 $f(i-1)$ 对应的那一段，这取决于 $nums[i]$ 和 $f(i−1)+nums[i]$ 的大小，取较大者，列出动态规划转移方程：
$$f(i) = \max { f(i-1) + nums[i], nums[i] }$$

数据结构：

• 变量maxf维护当前最大的$f(i)$
• 变量pre维护当前$f(i),f(i-1)

语法

forEach()
文档

对数组的每个元素执行一次给定的函数。

代码

var maxSubArray = function(nums) {
    let pre = 0, maxf = nums[0];
    nums.forEach((x) => {
        //选择f(i-1)+nums[i]还是nums[i]
        pre = Math.max(pre + x, x);
        //维护最大的f
        maxf = Math.max(maxf, pre);
    });
    return maxf;
};

复杂度分析：

时间复杂度O(n)、空间复杂度O(n)

解二：分治

思路：

自上而下：分解成子问题，求解子问题
自下而上：合并子问题

求a序列在区间[l,r]内的最大子段和
以m分开每一次取一半来解决，最大子段和可能出现在3个位置

• 左边内部
• 右边内部
• 包含了左边和右边的一部分

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */

getSubSum=function(nums,l,r){
    if (l===r) return nums[l];
    let m=parseInt((l+r)/2);
    //求左边内部
    let lsum=getSubSum(nums,l,m);
    //求右边内部
    let rsum=getSubSum(nums,m+1,r); 
    //求横跨左边和右边
    let ltemp=0,lmax=nums[m];
    //从右往左遍历左边的元素，维护累加器和最大值
    for(let i=m;i>=l;i--) {
        ltemp+=nums[i];
        if(ltemp>lmax) lmax=ltemp;
    }
    //从左往右遍历右边的元素，维护累加器和最大值
    let rtemp=0,rmax=nums[m+1];
    for(let i=m+1;i<=r;i++) {
        rtemp+=nums[i];
        if(rtemp>rmax) rmax=rtemp;
    }
    return Math.max(lsum,rsum,lmax+rmax);
};

var maxSubArray = function(nums) {
    return getSubSum(nums,0,nums.length-1);
};

复杂度分析

一共logn层，每一层全部扫描n
时间复杂度$O(n\log n)$