Maximum Subarray

由于簡(jiǎn)書(shū)不支持latex語(yǔ)法弄企，所以可以到下面的作業(yè)部落去看雪隧。
https://www.zybuluo.com/LIUHUAN/note/363545
標(biāo)簽（空格分隔）： algorithm

這個(gè)問(wèn)題我們先看下問(wèn)題的描述：

問(wèn)題描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray [4,?1,2,1] has the largest sum = 6.

問(wèn)題來(lái)自于Leetcode:Maximum Subarray

問(wèn)題分析

簡(jiǎn)單來(lái)說(shuō)额各，就是在一個(gè)數(shù)組中找到一個(gè)子數(shù)組使得
最大萝衩，也有找最小值的（可以轉(zhuǎn)化為找最大值的問(wèn)題豆村，不再詳述）

• 那么最直接的想法驼鞭，就是對(duì)于每一個(gè) 遍歷整個(gè)數(shù)組，用一個(gè)最大值標(biāo)記一下衫贬，就能都找到最大值了德澈。對(duì)于每一個(gè)組合總共有 個(gè)子數(shù)組，都遍歷一次數(shù)組固惯，那么可以看出來(lái)整個(gè)的復(fù)雜度為

解決方案

1.按著上面的思路梆造，我們可以寫(xiě)出如下的程序來(lái)

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        int max = 0x80000001;//最小的32位整數(shù)
        int sum = 0;
        for(int i =0;i<n;++i){
             for(int j=0;j<n;++j){
                 sum = 0;
                 /*計(jì)算 A[i,j] 的和*/
                 for(int k=i;k<=j;++k){
                    sum += nums[k]; 
                 }
                /**更新最大值max*/
                if(sum > max)
                    max = sum;
             }
        }
        return max;
    }

• 但是這種方法在Leetcode上面沒(méi)有通過(guò)，因?yàn)槌瑫r(shí)了葬毫。時(shí)間復(fù)雜度太高了镇辉。如果數(shù)據(jù)很大，那么會(huì)很慢贴捡。

2.上面的解決方案1需要重復(fù)計(jì)算每個(gè)子數(shù)組的部分過(guò)程

• 上面的算法我們每次是按著對(duì)來(lái)計(jì)算的忽肛，如果我們當(dāng)純來(lái)想如何求所有的子數(shù)組的過(guò)程，可以發(fā)現(xiàn)烂斋，對(duì)于一個(gè)特定的屹逛，我們可以計(jì)算的和础废，
  可以充分利用前面計(jì)算出來(lái)的 ,來(lái)降低時(shí)間復(fù)雜度。

• 那么就不用對(duì)于每一個(gè)都從到遍歷數(shù)組煎源，那么時(shí)間復(fù)雜度可以降低為
• 所以可以有如下優(yōu)化的代碼

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        int max = 0x80000001;//最小的32位整數(shù)
        int sum = 0;
        for(int i=0;i<n;++i){
            sum = 0;
            /**對(duì)于某個(gè)特定的i 分別計(jì)算A[i,i+1],A[i,i+2],...A[i,n-1]的和*/
            for(int j=i;j<n;++j){
                sum += nums[j];
                /**更新最大值max*/
                if(sum > max )
                    max = sum;
            }
        }
        return max;
}

• 噩耗再次傳來(lái)色迂，⊙﹏⊙b汗

• 沒(méi)有通過(guò)leetcode測(cè)試，還是超時(shí)了
• 那么看樣子時(shí)間復(fù)雜度還需要降低才可以手销。不然找不到工作了歇僧。。锋拖。

2.下面采用的分治的算法诈悍，從最大子數(shù)組出現(xiàn)的位置來(lái)考慮的∈薨＃可以參考<算法導(dǎo)論>的第4章內(nèi)容

• 分治的思想是侥钳，把數(shù)組看成兩個(gè)部分，可以認(rèn)為是從數(shù)組中間分割成
  和兩個(gè)數(shù)組柄错，那么我們的目標(biāo)就是通過(guò)求這兩個(gè)子數(shù)組的最大值舷夺，然后求得目前這個(gè)數(shù)組的最大子數(shù)組和的值。那么問(wèn)題來(lái)了售貌，如果你知道了的最大子數(shù)組的和和的最大子數(shù)組的和,你怎么求解目前這個(gè)數(shù)組的最大子數(shù)組的和给猾？⊙﹏⊙b汗

• 可以分析下，如果知道了和颂跨，那么我們分析下和的構(gòu)成敢伸。
• 
• 
• 從上面的表達(dá)式可以看出來(lái)是左邊的某個(gè)子數(shù)組的和， 是右邊的某個(gè)子數(shù)組的和恒削，具體是什么我們可以先不用管了池颈，因?yàn)椋@兩個(gè)值都是假設(shè)已經(jīng)知道的钓丰。
• 那么整個(gè) 最大子數(shù)組的和躯砰，出現(xiàn)的子數(shù)組的位置還有一種可能，那就是斑粱，在左邊有一部分弃揽，右邊也有一部分，并且包含這個(gè)元素则北。也就是子數(shù)組和的形式為，哎呦這樣看來(lái)不就是和之前形式一致了么痕慢？有神馬意義⊙﹏⊙b汗
• 客官尚揣，請(qǐng)慢！掖举！我明天再寫(xiě)吧快骗。
• 那么，我們就先分別遞歸求的左邊和右邊的最大子數(shù)組和的值，然后考慮下和當(dāng)前的跨越中點(diǎn)的那個(gè)最大子數(shù)組和進(jìn)行比較方篮，獲取他們?nèi)齻€(gè)當(dāng)中最大的那一個(gè)名秀。
• 那么如何求的跨越中點(diǎn)的子數(shù)組的最大值呢？
• 跨越中點(diǎn)有一個(gè)特點(diǎn)藕溅，就是左邊是以中點(diǎn)所在元素結(jié)尾匕得，右邊是以這個(gè)元素為開(kāi)始，那么由第二種解決方案的思路巾表，我們就可以分別從開(kāi)始汁掠，向左邊和右邊進(jìn)行遍歷找到最大的那個(gè)。其實(shí)這種遍歷是的復(fù)雜度的⊙﹏⊙b汗
• 那么我們就寫(xiě)下來(lái)代碼看看集币。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
    return maxSubArray_help(nums,0,n-1);
}

int maxSubArray_help(vector<int>& nums,int begin,int end){
    if(begin == end)
        return nums[end];
    int mid = (begin + end)>>1;
    /**左邊子數(shù)組的最大值子數(shù)組值*/
    int max_left = maxSubArray_help(nums,begin,mid);
    /**右邊子數(shù)組的最大值子數(shù)組值*/
    int max_right = maxSubArray_help(nums,mid + 1,end);
    /**跨越中點(diǎn)的最大值子數(shù)組值*/
    int max_cross = maxCrossMid(nums,begin,mid,end);
    return max(max(max_left,max_right),max_cross);
}

/*maxCrossMid函數(shù)的時(shí)間復(fù)雜度實(shí)際為O(n)*/
int maxCrossMid(vector<int>& nums,int begin,int mid ,int end){
    int left_max = 0x80000001;//最小的32位整數(shù)
    int right_max = 0x80000001;
    int sum = 0;
    /*計(jì)算以mid結(jié)尾的最大的子數(shù)組和考阱，左邊子數(shù)組*/
    for(int i = mid ;i>=begin;--i){
        sum += nums[i];
        if(sum > left_max)
            left_max = sum;
    }
    sum = 0;
    /*計(jì)算以mid+1開(kāi)始的最大的子數(shù)組和，右邊子數(shù)組*/
    for(int i=mid+1;i<=end;++i){
        sum += nums[i];
        if(sum > right_max)
            right_max = sum;
    }
    return left_max + right_max;
}

• 提交到Leetcode鞠苟，如果還通不過(guò)德玫，那么，你覺(jué)得我能找到工作么亿遂？黔驢技窮了都⊙﹏⊙b汗（還是參考算法導(dǎo)論的內(nèi)容）

• 好消息是通過(guò)了測(cè)試纯陨，壞消息是，運(yùn)行的速度很慢趾访。很慢态秧。。
• 我們來(lái)分析下這個(gè)算法慢在哪里,這個(gè)算法是一個(gè)分治的算法扼鞋，那么我們按著分治的思想列出時(shí)間復(fù)雜度的計(jì)算表達(dá)式,為什么最后面一項(xiàng)是,這項(xiàng)就表示我們計(jì)算跨越中點(diǎn)的最大子數(shù)組和的時(shí)間復(fù)雜度申鱼。 maxCrossMid這個(gè)函數(shù)的最壞情況下是最大子數(shù)組就是從begin開(kāi)始到end結(jié)束的和，那么begin和end最壞的情況就是0到n 所以時(shí)間復(fù)雜度是
• 那么這個(gè)表達(dá)式的結(jié)果是什么呢云头？
• 根據(jù)主定理捐友，我們可以知道這個(gè)解的下界是也就是,當(dāng)然這個(gè)算法比要快，不然也通不過(guò)測(cè)試溃槐。匣砖。
• 那么他們?cè)趺催\(yùn)行的那么快呢？有沒(méi)有線性時(shí)間的算法呢昏滴？

3.線性時(shí)間的算法,思想?yún)⒖妓惴▽?dǎo)論的第4章的習(xí)題

• 線性算法的思想是基于動(dòng)態(tài)規(guī)劃猴鲫，把問(wèn)題轉(zhuǎn)化為一個(gè)較小的子問(wèn)題。思考是這么想的谣殊，但是實(shí)際求解的過(guò)程還是從子問(wèn)題逐漸到整個(gè)問(wèn)題的過(guò)程拂共。我也不知道我在說(shuō)神馬⊙﹏⊙b汗

• 對(duì)于數(shù)組從左到右處理，記錄到目前為止姻几，他的意思是到你遍歷的某個(gè)元素為止的已經(jīng)處理過(guò)的最大子數(shù)組的宜狐，基于下面的觀察势告，如果已知的最大子數(shù)組，那么可以根據(jù)如下的性質(zhì)將解擴(kuò)展到為的最大子數(shù)組：的最大子數(shù)組抚恒，要么是的最大子數(shù)組咱台，要么是某個(gè)子數(shù)組俭驮。以結(jié)尾的子數(shù)組回溺。
• 那么我們可以想到，如果的最大子數(shù)組表鳍，和的最大子數(shù)組一樣馅而，那很好實(shí)現(xiàn)，但是這只是一種情況譬圣。其實(shí)重點(diǎn)在的子數(shù)組是，如果是這種情況怎么確定呢厘熟？也就是求解以結(jié)尾的最大子數(shù)組屯蹦，按著解決方案三的思想，我們可以從向左遍歷绳姨，求解一個(gè)最大的子數(shù)組登澜，但是這種很明顯就提高了復(fù)雜度，對(duì)于每一個(gè)你都要向左遍歷飘庄，那么時(shí)間復(fù)雜度就成為了⊙﹏⊙b汗
• 其實(shí)我們忘了一個(gè)假設(shè)脑蠕，那就是當(dāng)你處理到的時(shí)候，我們已經(jīng)知道以結(jié)尾的最大子數(shù)組跪削，對(duì)應(yīng)于算法導(dǎo)論中提到的記錄目前為止處理過(guò)的最大子數(shù)組谴仙。那么假設(shè)記錄以結(jié)尾的最大子數(shù)組，那么可以得到
  

• 這樣就把以結(jié)尾的最大子數(shù)組找出來(lái)了碾盐，那么到為止的最大子數(shù)組（可能不是以結(jié)尾）晃跺，還沒(méi)有找出來(lái)，這就需要我們從開(kāi)始記錄一個(gè)到為止的最大子數(shù)組毫玖，假設(shè)為表示到為止的最大子數(shù)組掀虎，然后和以結(jié)尾的最大子數(shù)組進(jìn)行比較，取最大的那個(gè)付枫，
  

• 這樣就可以完成求解到為止烹玉，最大的子數(shù)組。把過(guò)程弄明白之后阐滩，那就開(kāi)始寫(xiě)程序春霍。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
    vector<int> Max(n,0x80000001);
    vector<int> sum(n,0);
    sum[0] = nums[0];
    Max[0] = nums[0];
    for(int i=1;i<n;++i){
        /*以nums[i]結(jié)尾的最大子數(shù)組*/
        sum[i] = max(sum[i-1] + nums[i],nums[i]);
        /*到i為止的最大子數(shù)組*/
        Max[i] = max(sum[i],Max[i-1]);
    }
    /*返回到n-1為止的最大子數(shù)組，也就是整個(gè)數(shù)組的最大子數(shù)組*/
    return Max[n-1];
}

• Leetcode提交通過(guò)叶眉，速度任然很慢址儒，這是怎么一回事⊙﹏⊙b汗

• 分析下復(fù)雜度，時(shí)間復(fù)雜度為只掃描一遍數(shù)組衅疙。
• 空間復(fù)雜度為因?yàn)橛玫搅藘蓚€(gè)額外的數(shù)組Max和sum難道這個(gè)是慢的原因（有可能）
• 那么下面的思路就是對(duì)這個(gè)進(jìn)行優(yōu)化莲趣。

4.解決方案三的優(yōu)化

• 我們看著方案三的代碼，可以看出來(lái)饱溢，其實(shí)我們沒(méi)有必要把全局的最后求解的最大值和每次以為止的最大值分開(kāi)來(lái)求喧伞，只要存放在一個(gè)變量里面就可以了，因?yàn)榈?img class="math-inline" src="https://math.jianshu.com/math?formula=A_%7Bj%7D" alt="A_{j}" mathimg="1">為止的最大值只使用了一次就結(jié)束了绩郎，就在和以結(jié)尾的最大值進(jìn)行比較潘鲫，所以可以有下面的優(yōu)化一步的代碼。

  int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        vector<int> sum(n,0);
        sum[0] = nums[0];
        int max_sum = nums[0];
        for(int i=1;i<n;++i){
            /*以nums[i]結(jié)尾的最大子數(shù)組*/
            sum[i] = max(sum[i-1] + nums[i],nums[i]);
            /*到i為止的最大子數(shù)組*/
            max_sum = max(max_sum , sum[i]);
        }
        /*返回到n-1為止的最大子數(shù)組肋杖，也就是整個(gè)數(shù)組的最大子數(shù)組*/
        return max_sum;
}

5.解決方案四的進(jìn)一步優(yōu)化

• 在上一步的優(yōu)化當(dāng)中我們可以看出來(lái)溉仑，其實(shí)以結(jié)尾的最大子數(shù)組的值也是在求解以結(jié)尾的最大子數(shù)組的時(shí)候用到一次，其他的時(shí)候并不會(huì)用到状植，所以我們可以把這個(gè)sum數(shù)組也優(yōu)化了浊竟，具體的可以用變量，表示以結(jié)尾的最大子數(shù)組的和津畸，然后比較 和的大小振定，取最大的那個(gè)就代表到以結(jié)尾的最大子數(shù)組的和。

• 這樣我們就可以寫(xiě)出來(lái)肉拓，網(wǎng)上一般會(huì)直接給出的動(dòng)態(tài)規(guī)劃最后的結(jié)果后频。

• 當(dāng)然還有其他的寫(xiě)法，可以主要思想就是這樣暖途。

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        int sum_cur = nums[0];
        int max_sum = nums[0];
        for(int i=1;i<n;++i){
            /*以nums[i]結(jié)尾的最大子數(shù)組*/
            if(sum_cur < 0)
                sum_cur = nums[i];
            else 
                sum_cur += nums[i];
            /*到i為止的最大子數(shù)組*/
            if(sum_cur > max_sum)
                max_sum = sum_cur;
        }
        /*返回到n-1為止的最大子數(shù)組卑惜，也就是整個(gè)數(shù)組的最大子數(shù)組*/
        return max_sum;
}

6.總結(jié)

• 對(duì)于一個(gè)問(wèn)題首先要想到它最為直接，一般的方法丧肴，比如這個(gè)題的方案1和方案2残揉，首先想到這些直接的算法，然后觀察對(duì)這種方法進(jìn)行改進(jìn)芋浮。

• 我很不贊成直接給出最后一種優(yōu)化后的結(jié)果的答案抱环，因?yàn)檫@個(gè)比較難于理解，至少是對(duì)我來(lái)說(shuō)纸巷，如果你能直接看懂這個(gè)優(yōu)化后的結(jié)果镇草，那么可以用這種思想去做下Leetcode的Maximum Product Subarray這個(gè)題的思路和本題類似，后續(xù)的內(nèi)容也會(huì)寫(xiě)到這個(gè)題瘤旨。
• 曾經(jīng)發(fā)生過(guò)兩行代碼來(lái)解決這個(gè)問(wèn)題的爭(zhēng)論梯啤，確實(shí)優(yōu)化之后的核心代碼確實(shí)只有兩行，哈哈存哲。
• 對(duì)于沒(méi)見(jiàn)過(guò)的題因宇，弄懂別人的解法是學(xué)習(xí)七婴，能夠應(yīng)用之前學(xué)習(xí)到的方法解決問(wèn)題是能力

7.參考內(nèi)容

• 算法導(dǎo)論第4章

• Leetcode:Maximum Subarray