一、題目

給你一個整數(shù)數(shù)組nums，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。子數(shù)組 是數(shù)組中的一個連續(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 <= nums.length <= 105-104 <= nums[i] <= 104

進階： 如果你已經(jīng)實現(xiàn)復(fù)雜度為O(n)的解法，嘗試使用更為精妙的 分治法 求解。

二、代碼

【1】動態(tài)規(guī)劃： 假設(shè)nums數(shù)組的長度是n，下標從0到n−1。我們用f(i)代表以第i個數(shù)結(jié)尾的「連續(xù)子數(shù)組的最大和」，那么很顯然我們要求的答案就是：max?0≤i≤n−1{f(i)}因此我們只需要求出每個位置的f(i)，然后返回f數(shù)組中的最大值即可。那么我們?nèi)绾吻?code>f(i)呢？我們可以考慮nums[i]單獨成為一段還是加入f(i−1)對應(yīng)的那一段，這取決于nums[i]和f(i−1)+nums[i]的大小，我們希望獲得一個比較大的，于是可以寫出這樣的動態(tài)規(guī)劃轉(zhuǎn)移方程：f(i)=max?{f(i−1)+nums[i],nums[i]}不難給出一個時間復(fù)雜度O(n)、空間復(fù)雜度O(n)的實現(xiàn)，即用一個f數(shù)組來保存f(i)的值，用一個循環(huán)求出所有f(i)。考慮到f(i)只和f(i−1)相關(guān)，于是我們可以只用一個變量pre來維護對于當前f(i)的f(i−1)的值是多少，從而讓空間復(fù)雜度降低到O(1)，這有點類似「滾動數(shù)組」的思想。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

時間復(fù)雜度： O(n)，其中n為nums數(shù)組的長度。我們只需要遍歷一遍數(shù)組即可求得答案。

空間復(fù)雜度： O(1)。我們只需要常數(shù)空間存放若干變量。

【2】分治： 這個分治方法類似于「線段樹求解最長公共上升子序列問題」的pushUp操作。 也許讀者還沒有接觸過線段樹，沒有關(guān)系，方法二的內(nèi)容假設(shè)你沒有任何線段樹的基礎(chǔ)。當然，如果讀者有興趣的話，推薦閱讀線段樹區(qū)間合并法解決多次詢問的「區(qū)間最長連續(xù)上升序列問題」和「區(qū)間最大子段和問題」，還是非常有趣的。

我們定義一個操作get(a, l, r)表示查詢a序列[l,r]區(qū)間內(nèi)的最大子段和，那么最終我們要求的答案就是get(nums, 0, nums.size() - 1)。如何分治實現(xiàn)這個操作呢？對于一個區(qū)間[l,r]，我們?nèi)?code>m=⌊l+r2⌋，對區(qū)間[l,m]和[m+1,r]分治求解。當遞歸逐層深入直到區(qū)間長度縮小為1的時候，遞歸「開始回升」。這個時候我們考慮如何通過[l,m]區(qū)間的信息和[m+1,r]區(qū)間的信息合并成區(qū)間[l,r]的信息。最關(guān)鍵的兩個問題是：

1、我們要維護區(qū)間的哪些信息呢？

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

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

1、lSum表示[l,r]內(nèi)以l為左端點的最大子段和

2、rSum表示[l,r]內(nèi)以r為右端點的最大子段和

3、mSum表示[l,r]內(nèi)的最大子段和

4、iSum表示[l,r]的區(qū)間和

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

1、首先最好維護的是iSum，區(qū)間[l,r]的iSum就等于「左子區(qū)間」的iSum加上「右子區(qū)間」的iSum。

2、對于[l,r]的lSum，存在兩種可能，它要么等于「左子區(qū)間」的lSum，要么等于「左子區(qū)間」的iSum加上「右子區(qū)間」的lSum，二者取大。

3、對于[l,r]的rSum，同理，它要么等于「右子區(qū)間」的rSum，要么等于「右子區(qū)間」的iSum加上「左子區(qū)間」的rSum，二者取大。

4、當計算好上面的三個量之后，就很好計算[l,r]的mSum了。我們可以考慮[l,r]的mSum對應(yīng)的區(qū)間是否跨越m——它可能不跨越m，也就是說[l,r]的mSum可能是「左子區(qū)間」的mSum和 「右子區(qū)間」的mSum中的一個；它也可能跨越m，可能是「左子區(qū)間」的rSum和 「右子區(qū)間」的lSum求和。三者取大。

這樣問題就得到了解決。

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

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

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

假設(shè)序列a的長度為n。

時間復(fù)雜度： 假設(shè)我們把遞歸的過程看作是一顆二叉樹的先序遍歷，那么這顆二叉樹的深度的漸進上界為O(log?n)，這里的總時間相當于遍歷這顆二叉樹的所有節(jié)點，故總時間的漸進上界是O(∑i=1log?n2i−1)=O(n)，故漸進時間復(fù)雜度為O(n)。

空間復(fù)雜度： 遞歸會使用O(log?n)的?？臻g，故漸進空間復(fù)雜度為O(log?n)。

題外話： 「方法二」相較于「方法一」來說，時間復(fù)雜度相同，但是因為使用了遞歸，并且維護了四個信息的結(jié)構(gòu)體，運行的時間略長，空間復(fù)雜度也不如方法一優(yōu)秀，而且難以理解。那么這種方法存在的意義是什么呢？

對于這道題而言，確實是如此的。但是仔細觀察「方法二」，它不僅可以解決區(qū)間[0,n−1]，還可以用于解決任意的子區(qū)間[l,r]的問題。如果我們把[0,n−1]分治下去出現(xiàn)的所有子區(qū)間的信息都用堆式存儲的方式記憶化下來，即建成一棵真正的樹之后，我們就可以在O(log?n)的時間內(nèi)求到任意區(qū)間內(nèi)的答案，我們甚至可以修改序列中的值，做一些簡單的維護，之后仍然可以在O(log?n)的時間內(nèi)求到任意區(qū)間內(nèi)的答案，對于大規(guī)模查詢的情況下，這種方法的優(yōu)勢便體現(xiàn)了出來。這棵樹就是上文提及的一種神奇的數(shù)據(jù)結(jié)構(gòu)——線段樹。

總結(jié)

到此這篇關(guān)于最大子數(shù)組和Java實現(xiàn)的文章就介紹到這了,更多相關(guān)最大子數(shù)組和Java內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論