题目描述
给你一个整数数组 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:动态规划
设 dp[i] 为以i点为结尾的最大子序和
dp[i]有两种状态，一种是nums[i]单独作为一个子序列和，一种是nums[i] 和dp[i-1] 和在一起作为子序列和
因而dp[i]的动态转移方程为：
dp[i] = max(dp[i-1] + nums[i],nums[i])
边界条件dp[0] = nums[0]
// OC
+ (int)maxSubArray1:(NSArray *)nums {
int n = (int)nums.count;
if (n == 0) {
return 0;
}
int maxAns = 0;
int dp[n];
dp[0] = [nums[0] intValue];
maxAns = dp[0];
for (int i=1; i<n; i++) {
dp[i] = MAX(dp[i-1]+[nums[i] intValue], [nums[i] intValue]);
if (dp[i] > maxAns) {
maxAns = dp[i];
}
}
return maxAns;
}
// Swift
static public func maxSubArray1(_ nums: [Int]) -> Int {
let n = nums.count
if n == 0 {return 0}
var dp = Array(repeating: 0, count: n)
dp[0] = nums[0]
var maxAns = dp[0]
for i in 1..<n {
dp[i] = max(dp[i-1]+nums[i], nums[i])
maxAns = max(dp[i], maxAns)
}
return maxAns
}
优化上述逻辑
由于dp[i] 只和 dp[i-1] 相关，我们可以只用一个变量pre来维护dp[i-1] dp[i]的值
// OC
+ (int)maxSubArray2:(NSArray *)nums {
int n = (int)nums.count;
if (n == 0) {
return 0;
}
int maxAns = [nums[0] intValue];
int pre = 0;
for (int i=0; i<n; i++) {
pre = MAX(pre+[nums[i] intValue], [nums[i] intValue]);
if (pre > maxAns) {
maxAns = pre;
}
}
return maxAns;
}
// Swift
static public func maxSubArray2(_ nums: [Int]) -> Int {
let n = nums.count
if n == 0 {return 0}
var maxAns = nums[0]
var pre = nums[0]
for i in 1..<n {
pre = max(pre+nums[i], nums[i])
maxAns = max(pre, maxAns)
}
return maxAns
}
思路2:分治
这个分治方法类似于「线段树求解最长公共上升子序列问题」的 pushUp 操作
我们定义一个操作 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,m] 区间的信息和[m+1,r] 区间的信息合并成区间[l,r] 的信息。最关键的两个问题是：
我们要维护区间的哪些信息呢？
-
我们如何合并这些信息呢？
对于一个区间[l,r]，我们可以维护四个量：
- lSum 表示[l,r] 内以l 为左端点的最大子段和
- rSum 表示[l,r] 内以r 为右端点的最大子段和
- mSum 表示[l,r] 内的最大子段和
- iSum 表示[l,r] 的区间和
以下简称[l,m] 为[l,r] 的「左子区间」，[m+1,r] 为[l,r] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到[l,r] 的信息）？
对于长度为1 的区间[i,i]，四个量的值都和nums[i] 相等。对于长度大于1 的区间：- 首先最好维护的是iSum，区间[l,r] 的iSum 就等于「左子区间」的iSum 加上「右子区间」的iSum
- 对于[l,r] 的lSum，存在两种可能，它要么等于「左子区间」的lSum，要么等于「左子区间」的iSum 加上「右子区间」的lSum，二者取大
- 对于[l,r] 的rSum，同理，它要么等于「右子区间」的rSum，要么等于「右子区间」的iSum 加上「左子区间」的rSum，二者取大
- 当计算好上面的三个量之后，就很好计算[l,r] 的mSum 了。我们可以考虑[l,r] 的mSum 对应的区间是否跨越m——它可能不跨越m，也就是说[l,r] 的mSum 可能是「左子区间」的mSum 和 「右子区间」的mSum 中的一个；它也可能跨越m，可能是「左子区间」的rSum 和 「右子区间」的lSum 求和。三者取大
// OC
typedef struct {
int iSum, lSum, rSum, mSum;
} DCStatus;
+ (DCStatus)pushUp:(DCStatus)l r:(DCStatus)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 (DCStatus){iSum,lSum,rSum,mSum};
}
+ (DCStatus)getMaxSubArray:(NSArray *)nums l:(int)l r:(int)r {
if (l==r) {
return (DCStatus){[nums[l] intValue],[nums[l] intValue],[nums[l] intValue],[nums[l] intValue]};
}
int m = (l+r)/2;
DCStatus lSub = [self getMaxSubArray:nums l:l r:m];
DCStatus rSub = [self getMaxSubArray:nums l:m+1 r:r];
return [self pushUp:lSub r:rSub];
}
+ (int)maxSubArray3:(NSArray *)nums {
int n = (int)nums.count;
if (n == 0) {
return 0;
}
DCStatus resStatus = [self getMaxSubArray:nums l:0 r:n-1];
return resStatus.mSum;
}
// Swift
struct DCStatus {
var iSum:Int
var lSum:Int
var rSum:Int
var mSum:Int
}
static func pushUp(_ l:DCStatus, _ r:DCStatus) -> DCStatus {
let iSum = l.iSum + r.iSum
let lSum = max(l.lSum, l.iSum + r.lSum)
let rSum = max(r.rSum, r.iSum + l.rSum)
let mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum)
return DCStatus(iSum: iSum, lSum: lSum, rSum: rSum, mSum: mSum)
}
static func getMaxSubArray(_ nums: [Int], _ l:Int, _ r:Int) -> DCStatus {
if l == r {
return DCStatus(iSum: nums[l], lSum: nums[l], rSum: nums[l], mSum: nums[l])
}
let m = (l+r)/2
let lSub = getMaxSubArray(nums, l, m)
let rSub = getMaxSubArray(nums, m+1, r)
return pushUp(lSub, rSub)
}
static public func maxSubArray3(_ nums: [Int]) -> Int {
let n = nums.count
if n == 0 {return 0}
let res:DCStatus = getMaxSubArray(nums, 0, n-1)
return res.mSum
}
参考：https://leetcode-cn.com/problems/maximum-subarray
https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
