最大子序和

问题

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

示例：

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

// 示例 2
输入: nums = [1]
输出: 1

// 示例 3
输入: nums = [5,4,-1,7,8]
输出: 23

约束条件：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

解答

方法一：动态规划

用 f(i) 表示以第 i 个数结尾的连续子数组的最大和。对于每个位置，我们需要决定是将当前元素加入前面的子数组，还是从当前元素重新开始。

状态转移方程：

f(i) = max(f(i-1) + nums[i], nums[i])

使用滚动变量优化空间复杂度：

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

复杂度分析：

• 时间复杂度：O(n)，遍历一遍数组
• 空间复杂度：O(1)，只使用常数空间

方法二：分治法

对于区间 [l, r]，维护四个量：

• lSum：以左端点为起点的最大子段和
• rSum：以右端点为终点的最大子段和
• mSum：区间内的最大子段和
• iSum：区间总和

通过递归分治，将区间从中点分为左右两部分，然后合并信息。

function Status(l, r, m, i) {
    this.lSum = l;
    this.rSum = r;
    this.mSum = m;
    this.iSum = i;
}

const pushUp = (l, r) => {
    const iSum = l.iSum + r.iSum;
    const lSum = Math.max(l.lSum, l.iSum + r.lSum);
    const rSum = Math.max(r.rSum, r.iSum + l.rSum);
    const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
    return new Status(lSum, rSum, mSum, iSum);
}

const getInfo = (a, l, r) => {
    if (l === r) {
        return new Status(a[l], a[l], a[l], a[l]);
    }
    const m = (l + r) >> 1;
    const lSub = getInfo(a, l, m);
    const rSub = getInfo(a, m + 1, r);
    return pushUp(lSub, rSub);
}

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

复杂度分析：

• 时间复杂度：O(n)，相当于遍历二叉树的所有节点
• 空间复杂度：O(log n)，递归栈空间

分治法的优势： 虽然对于单次查询，分治法不如动态规划简洁，但它可以扩展为线段树结构，支持在 O(log n) 时间内查询任意子区间的最大子段和，以及动态修改数组元素，适合大规模查询场景。

关键点

• 动态规划的核心是判断当前元素是加入前面的子数组还是独立成段，取决于 pre + x 和 x 的大小关系
• 使用滚动变量可以将空间复杂度从 O(n) 优化到 O(1)
• 分治法需要维护四个量（lSum、rSum、mSum、iSum）来合并左右子区间的信息
• 分治法可以扩展为线段树，支持区间查询和动态修改操作