LeetCode-53. 最大子序和

53. 最大子序和

給定一個(gè)整數(shù)數(shù)組 nums ,找到一個(gè)具有最大和的連續(xù)子數(shù)組(子數(shù)組最少包含一個(gè)元素)捅暴,返回其最大和伸眶。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大肛冶,為 6览徒。

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


  • 1-暴力:n^2
  • 2-DP:
    a.分治(子問題) max_sum(i) = Max(max_sum(i - 1), 0) + a[i]
    b.狀態(tài)數(shù)組: f[i]
    c.DP方程:f[i] = Max(f[i - 1] , 0) + a[i]
  1. dp問題:
    dp公式:dp[i] = max(nums[i] , nums[i] + dp[i - 1])
    提取出nums[i] :dp[i] = max( 0 , dp[i - 1]) + nums[i]
    //nums[i - 1]代表dp[i - 1]
    nums[i] = max(0 , nums[i - 1]) + nums[i]

  2. 最大子序和 = 當(dāng)前元素自身最大(負(fù)的)币励,或者 包含之前(正的)后最大

參考:
https://leetcode-cn.com/problems/maximum-subarray/solution/javashi-xian-dong-tai-gui-hua-fang-fa-by-zhengzhon/

https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length]; // 存儲(chǔ)以i為結(jié)尾的最大子序列和
        dp[0] = nums[0]; // 第0個(gè)元素最大序列和為nums[0]
        int maxSum = nums[0]; // 最大子序列和
        // 遍歷整個(gè)素組,獲取以i為結(jié)尾的最大子序列和
        // 當(dāng)dp[i-1]>0時(shí)珊拼,dp[i]=nums[i]+dp[i-1]
        // 當(dāng)dp[i-1]<=0時(shí),dp[i]=nums[i]
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            // 每次比較dp[i]和maxSum取最大值
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }

簡(jiǎn)化if else 判斷:

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length]; // 存儲(chǔ)以i為結(jié)尾的最大子序列和
        dp[0] = nums[0]; // 第0個(gè)元素最大序列和為nums[0]
        int maxSum = nums[0]; // 最大子序列和
        // 遍歷整個(gè)素組食呻,獲取以i為結(jié)尾的最大子序列和
        // 當(dāng)dp[i-1]>0時(shí),dp[i]=nums[i]+dp[i-1]
        // 當(dāng)dp[i-1]<=0時(shí),dp[i]=nums[i]
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(0, dp[i - 1]) + nums[i];
//          if (dp[i - 1] > 0) {
//              dp[i] = dp[i - 1] + nums[i];
//          } else {
//              dp[i] = nums[i];
//          }
            // 每次比較dp[i]和maxSum取最大值
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }

不新增dp數(shù)組澎现,直接使用nums數(shù)組

    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // 最大子序列和
        for (int i = 1; i < nums.length; i++) {
            nums[i] = Math.max(0, nums[i - 1]) + nums[i];
            maxSum = Math.max(maxSum, nums[i]);
        }
        return maxSum;
    }

對(duì)于上面的代碼仅胞,也可以使用lastSum來記錄nums[i-1]為結(jié)尾的最大連續(xù)子序列和

    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // 最大子序列和
        int lastSum = nums[0];//假設(shè)當(dāng)前索引為i,則lastSum保存以nums[i-1]為結(jié)尾的最大連續(xù)子序列和
        // 遍歷整個(gè)素組,獲取以nums[i]為結(jié)尾的最大子序列和
        for (int i = 1; i < nums.length; i++) {
            lastSum = Math.max(0, lastSum) + nums[i];
            maxSum = Math.max(maxSum, lastSum); // 每次比較lastSum和maxSum取最大值
        }
        return maxSum;
    }
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末剑辫,一起剝皮案震驚了整個(gè)濱河市干旧,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌妹蔽,老刑警劉巖椎眯,帶你破解...
    沈念sama閱讀 222,627評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異胳岂,居然都是意外死亡编整,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,180評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門乳丰,熙熙樓的掌柜王于貴愁眉苦臉地迎上來掌测,“玉大人,你說我怎么就攤上這事产园」” “怎么了?”我有些...
    開封第一講書人閱讀 169,346評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵什燕,是天一觀的道長(zhǎng)粘勒。 經(jīng)常有香客問我,道長(zhǎng)屎即,這世上最難降的妖魔是什么仲义? 我笑而不...
    開封第一講書人閱讀 60,097評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮,結(jié)果婚禮上埃撵,老公的妹妹穿的比我還像新娘。我一直安慰自己虽另,他們只是感情好暂刘,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,100評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著捂刺,像睡著了一般谣拣。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上族展,一...
    開封第一講書人閱讀 52,696評(píng)論 1 312
  • 那天森缠,我揣著相機(jī)與錄音,去河邊找鬼仪缸。 笑死贵涵,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的恰画。 我是一名探鬼主播宾茂,決...
    沈念sama閱讀 41,165評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼拴还!你這毒婦竟也來了跨晴?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,108評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤片林,失蹤者是張志新(化名)和其女友劉穎端盆,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體费封,經(jīng)...
    沈念sama閱讀 46,646評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡焕妙,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,709評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了孝偎。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片访敌。...
    茶點(diǎn)故事閱讀 40,861評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖衣盾,靈堂內(nèi)的尸體忽然破棺而出寺旺,到底是詐尸還是另有隱情,我是刑警寧澤势决,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布阻塑,位于F島的核電站,受9級(jí)特大地震影響果复,放射性物質(zhì)發(fā)生泄漏陈莽。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,196評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望走搁。 院中可真熱鬧独柑,春花似錦、人聲如沸私植。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,698評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽曲稼。三九已至索绪,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間贫悄,已是汗流浹背瑞驱。 一陣腳步聲響...
    開封第一講書人閱讀 33,804評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留窄坦,地道東北人唤反。 一個(gè)月前我還...
    沈念sama閱讀 49,287評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像嫡丙,于是被迫代替她去往敵國(guó)和親拴袭。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,860評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容