每日一道 LeetCode (12)：最大子序和（文末送福利）
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題外話
周末了，今天先聊點(diǎn)題外話，能打開看這篇文章的絕對是真愛了，雖然這個(gè)閱讀量每天看的我心臟病都要出來了。
前兩天恰了點(diǎn)飯，首先感謝各位這么長時(shí)間以來一直對我的支持，思來想去，給大家發(fā)點(diǎn)紅包，雖然錢不多，不過我這篇文章點(diǎn)開看的人也不多，中獎(jiǎng)率應(yīng)該還算可以，中獎(jiǎng)的同學(xué)晚飯加個(gè)雞腿可樂啥的應(yīng)該是夠了。
紅包是無套路的那種，點(diǎn)了以后等開獎(jiǎng)就好了，還希望大家以后能多點(diǎn)點(diǎn)再看和轉(zhuǎn)發(fā)。
別多想，我就是單純的想要賄賂你們。
題目：最大子序和
題目來源：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
給定一個(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) 的解法，嘗試使用更為精妙的分治法求解。
解題思路
這道題有點(diǎn)意思，一開始我看著不難，但是嘗試了幾次解題，發(fā)現(xiàn)總有哪里不對。
動態(tài)規(guī)劃
直接打開答案，看到解析，才知道這道題涉及到一個(gè)叫做動態(tài)規(guī)劃的東西。
「動態(tài)規(guī)劃(dynamic programming)」 是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。
?動態(tài)規(guī)劃實(shí)際上是一類題目的總稱，并不是指某個(gè)固定的算法。動態(tài)規(guī)劃的意義就是通過采用遞推（或者分而治之）的策略，通過解決大問題的子問題從而解決整體的做法。動態(tài)規(guī)劃的核心思想是巧妙的將問題拆分成多個(gè)子問題，通過計(jì)算子問題而得到整體問題的解。而子問題又可以拆分成更多的子問題，從而用類似遞推迭代的方法解決要求的問題。
?
問題定義
這道題的題目是要求我們?nèi)デ笠粋€(gè)數(shù)列中最大連續(xù)子序列的和。
稍稍轉(zhuǎn)變一下目標(biāo)，我們把上面這個(gè)定義轉(zhuǎn)變一下，轉(zhuǎn)變成：
?Fk 是第 k 項(xiàng)前的最大序列和，求 F1 ～ FN 中最大值。
?
問題轉(zhuǎn)化到這一步，接著往下想，對于前 k 個(gè)項(xiàng)的最大子序列和，其實(shí)是在求前 k-1 項(xiàng)的最大子序列和與第 k 項(xiàng)的和，或者是與第 k 項(xiàng)相比兩者中較大的。
如果沒有理解的同學(xué)，可以參考下面的代碼，我也是看了這段代碼才明白了這個(gè)含義。
解題答案
先上代碼，代碼其實(shí)很簡潔：
public?int?maxSubArray(int[]?nums)?{
????//?定義前?k?-1?項(xiàng)最大和?pre?與最大和?maxAns
????int?pre?=?0,?maxAns?=?nums[0];
????for?(int?i?=?0;?i?????????//?獲取前?k?-1?項(xiàng)最大和
????????pre?=?Math.max(pre?+?nums[i],?nums[i]);
????????//?比較前?k?-1?項(xiàng)最大和與當(dāng)前最大和
????????maxAns?=?Math.max(maxAns,?pre);
????}
????return?maxAns;
}
這段代碼本身并不好理解，需要自己手動多 debug 幾次。文末有紅包，別忘了領(lǐng)。
