vlambda博客
学习文章列表

本节为动态规划第四题：最大子序和(maximum-subarray)，主要包括：问题描述，算法思路，复杂度分析，C++实现。

1. 问题描述

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

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

2. 解法

2.1 动态规划

  这样不难写出一个时间和空间复杂度为O(n)实现，但是f(i)只与f(i-1)相关，所以我们可以只用一个变量pre来维护当前f(i)对应的f(i-1)的值，从而降低空间复杂度为O(1)，C++代码如下：

//1. 动态规划解法，时间复杂度O(n)，空间复杂度O(1) int maxSubArray(vector<int>& nums) { int pre = 0, maxAns = nums[0]; for (const auto& x : nums) { pre = max(pre + x, x); maxAns = max(maxAns, pre); } return maxAns; }

2.2 分治法

  定义一个操作get(a,l,r)，表示查询a序列[l,r]区间内的最大字段和，那么我们要求的就是get(nums,0,nums.size()-1)。
  用分治法实现这个操作，对于一个区间[l,r]，m=下取整((l+r)/2)，对区间[l,m]和[m+1,r]的分治求解，当递归逐层深入直到区间长度缩小为1的时候，递归开始回升，这个时候考虑如何通过两个区间的信息合并成区间[l,r]的信息，有两个关键点：

• 如何维护区间的那些信息

• 如何合并这些信息
    对于一个区间[l,r]，我们可以维护四个量：

• lSum：表示[l,r]内以l为左端点的最大子段和

• rSum：表示[l,r]内以r为右端点的最大子段和

• mSUm：表示[l,r]内的最大字段和

• iSum：表示[l,r]的区间和

  以下简称[l,m]为[l,r]的左子区间，对于长度大于1的区间：

• 首先最好维护的是iSum，区间[l,r]的iSum就等于左子区间的iSum加上右子区间的iSum

• 对于[l,r]的lSum，存在两种可能，要么等于左子区间的lSum，要么等于左子区间的iSum加上右子区间的lSum，二者取较大者

• rSum同理要么等于右子区间的rSum，要么等于右子区间的iSum加上左子区间的rSum，二者取较大者

• 有了上面三个量[l,r]的mSum可能是左子区间的mSum和右子区间的mSum中的一个，也有可能是左子区间的rSum和右子区间的lSum求和，三者取大。

  这样的方法时间复杂度相同，由于使用递归，空间复杂度更大，它存在的意义是这种方法不仅可以解决区间[0,n-1]，它可以解决任意子区间的问题，如果我们把[0,n-1]分治下取出现的所有子区间的信息都用堆式存储的方式记忆化下来，建立成一颗真正的树，我们就可以在O(logn)时间找到任意区间的答案，甚至可以修改序列的值做一些简单的维护。对于大规模的查询问题，这种方法的优势便得以体现，这棵树也就是线段树。

  C++代码：

//2. 分治法，时间复杂度O(n)，空间复杂度O(logn)。 struct Status { int lSum, rSum, mSum, iSum; }; Status pushUp(Status l, Status r) { int iSum = l.iSum + r.iSum; int lSum = max(l.lSum, l.iSum + r.lSum); int rSum = max(r.rSum, r.iSum + l.rSum); int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum); return Status{ lSum, rSum, mSum, iSum }; } Status get(vector<int>& a, int l, int r) { if (l == r) return Status{ a[1], a[1], a[1], a[1] }; int m = (1 + r) >> 1; Status lSub = get(a, 1, m); Status rSub = get(a, m + 1, r); return pushUp(lSub, rSub); } int maxSubArray(vector<int>& nums) { return get(nums, 0, nums.size() - 1).mSum; }