題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，請(qǐng)你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

子數(shù)組 是數(shù)組中的一個(gè)連續(xù)部分。

示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。

示例 2：
輸入：nums = [1]
輸出：1

示例 3：
輸入：nums = [5,4,-1,7,8]
輸出：23

題解

思路1:動(dòng)態(tài)規(guī)劃

設(shè) dp[i] 為以i點(diǎn)為結(jié)尾的最大子序和

dp[i]有兩種狀態(tài)，一種是nums[i]單獨(dú)作為一個(gè)子序列和，一種是nums[i] 和dp[i-1] 和在一起作為子序列和
因而dp[i]的動(dòng)態(tài)轉(zhuǎn)移方程為：
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
        
    }

優(yōu)化上述邏輯
由于dp[i] 只和 dp[i-1] 相關(guān)，我們可以只用一個(gè)變量pre來(lái)維護(hù)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:分治

這個(gè)分治方法類(lèi)似于「線段樹(shù)求解最長(zhǎng)公共上升子序列問(wèn)題」的 pushUp 操作

我們定義一個(gè)操作 get(a, l, r) 表示查詢a 序列[l,r] 區(qū)間內(nèi)的最大子段和，那么最終我們要求的答案就是 get(nums, 0, nums.size() - 1)

如何分治實(shí)現(xiàn)這個(gè)操作呢？對(duì)于一個(gè)區(qū)間[l,r]，我們?nèi)= (l+r)/2，對(duì)區(qū)間[l,m] 和[m+1,r] 分治求解。當(dāng)遞歸逐層深入直到區(qū)間長(zhǎng)度縮小為1的時(shí)候，遞歸「開(kāi)始回升」。這個(gè)時(shí)候我們考慮如何通過(guò)[l,m] 區(qū)間的信息和[m+1,r] 區(qū)間的信息合并成區(qū)間[l,r] 的信息。最關(guān)鍵的兩個(gè)問(wèn)題是：

• 我們要維護(hù)區(qū)間的哪些信息呢？

• 我們?nèi)绾魏喜⑦@些信息呢？

  對(duì)于一個(gè)區(qū)間[l,r]，我們可以維護(hù)四個(gè)量：

  • lSum 表示[l,r] 內(nèi)以l 為左端點(diǎn)的最大子段和
  • rSum 表示[l,r] 內(nèi)以r 為右端點(diǎn)的最大子段和
  • mSum 表示[l,r] 內(nèi)的最大子段和
  • iSum 表示[l,r] 的區(qū)間和

  以下簡(jiǎn)稱[l,m] 為[l,r] 的「左子區(qū)間」，[m+1,r] 為[l,r] 的「右子區(qū)間」。我們考慮如何維護(hù)這些量呢（如何通過(guò)左右子區(qū)間的信息合并得到[l,r] 的信息）？
  對(duì)于長(zhǎng)度為1 的區(qū)間[i,i]，四個(gè)量的值都和nums[i] 相等。對(duì)于長(zhǎng)度大于1 的區(qū)間：

  • 首先最好維護(hù)的是iSum，區(qū)間[l,r] 的iSum 就等于「左子區(qū)間」的iSum 加上「右子區(qū)間」的iSum
  • 對(duì)于[l,r] 的lSum，存在兩種可能，它要么等于「左子區(qū)間」的lSum，要么等于「左子區(qū)間」的iSum 加上「右子區(qū)間」的lSum，二者取大
  • 對(duì)于[l,r] 的rSum，同理，它要么等于「右子區(qū)間」的rSum，要么等于「右子區(qū)間」的iSum 加上「左子區(qū)間」的rSum，二者取大
  • 當(dāng)計(jì)算好上面的三個(gè)量之后，就很好計(jì)算[l,r] 的mSum 了。我們可以考慮[l,r] 的mSum 對(duì)應(yīng)的區(qū)間是否跨越m——它可能不跨越m，也就是說(shuō)[l,r] 的mSum 可能是「左子區(qū)間」的mSum 和 「右子區(qū)間」的mSum 中的一個(gè)；它也可能跨越m，可能是「左子區(qū)間」的rSum 和 「右子區(qū)間」的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/