快捷導(dǎo)航

最大子數(shù)組和Java實(shí)現(xiàn)代碼示例

更新時(shí)間：2024年11月21日 08:31:28 作者：程序猿進(jìn)階

這篇文章主要介紹了最大子數(shù)組和Java實(shí)現(xiàn)的相關(guān)資料,文中介紹了兩種方法來解決尋找具有最大和的連續(xù)子數(shù)組的問題,第一種方法是動(dòng)態(tài)規(guī)劃,第二種方法是分治法,需要的朋友可以參考下

一、題目

給你一個(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 <= nums.length <= 105-104 <= nums[i] <= 104

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

二、代碼

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

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

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

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

我們定義一個(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)?code>m=⌊l+r2⌋，對(duì)區(qū)間[l,m]和[m+1,r]分治求解。當(dāng)遞歸逐層深入直到區(qū)間長(zhǎng)度縮小為1的時(shí)候，遞歸「開始回升」。這個(gè)時(shí)候我們考慮如何通過[l,m]區(qū)間的信息和[m+1,r]區(qū)間的信息合并成區(qū)間[l,r]的信息。最關(guān)鍵的兩個(gè)問題是：

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

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

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

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

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

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

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

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

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

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

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

4、當(dāng)計(jì)算好上面的三個(gè)量之后，就很好計(jì)算[l,r]的mSum了。我們可以考慮[l,r]的mSum對(duì)應(yīng)的區(qū)間是否跨越m——它可能不跨越m，也就是說[l,r]的mSum可能是「左子區(qū)間」的mSum和「右子區(qū)間」的mSum中的一個(gè)；它也可能跨越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的長(zhǎng)度為n。

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

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

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

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