題目：
題目鏈接https://leetcode-cn.com/problems/maximum-subarray/description/
背景：
????????本題為非常經(jīng)典的一道算法入門(mén)題，有著多種非常高效的解題方法，可以幫助答題感受到“找到問(wèn)題的關(guān)鍵與解決問(wèn)題的核心最小點(diǎn)”這個(gè)思維的關(guān)鍵与帆。
????????原本覺(jué)得此題很簡(jiǎn)單纺且，也很容易給同事們講清楚。實(shí)際在講的時(shí)候發(fā)現(xiàn)自己也并沒(méi)有把所有的方法的根本原理徹底想清楚整陌，所以在此做一個(gè)完整的整理與分析锁荔，供自己以后回憶、以及讓大家更好的理解黎做。
? ? ? ? 在此給大家分享五種解法叉跛，歡迎一起討論以及使用其它方法實(shí)現(xiàn)。
一蒸殿、無(wú)暴力筷厘，不解題
? ? ? ? 作為個(gè)人習(xí)慣，遇到一個(gè)問(wèn)題總是喜歡先考慮能否用暴力方法解決問(wèn)題宏所。因?yàn)楸┝Ψ椒ǖ乃季S方式最為簡(jiǎn)單酥艳，并不需要過(guò)多的考慮問(wèn)題背后所蘊(yùn)含的原理與思路。而且在實(shí)際生活中爬骤，可能很多問(wèn)題我們使用暴力方式就足夠了玖雁，這樣會(huì)給開(kāi)發(fā)以及運(yùn)維人員都大大減少工作量盖腕。
方法一赫冬，暴力到底：
? ? ? ? 題目要求是找出最大子序和，那么我們就把所有的子序都找出來(lái)溃列，并且求出每個(gè)子序的和然后找到最大的一個(gè)就可以了劲厌。題目已給一個(gè)序列，我們需要做的就是確定所有能找到的開(kāi)始序號(hào)與結(jié)束序號(hào)听隐，然后把這個(gè)序號(hào)中的所有子序和都求出來(lái)补鼻。具體實(shí)現(xiàn)如下：
????????此方法中我們用了三層循環(huán)，即在確定了某一個(gè)子序的開(kāi)始序號(hào)（i）與結(jié)束序號(hào)（j）的位置后雅任，枚舉i與j中間的每個(gè)點(diǎn)k风范，計(jì)算從i到k的子序和，時(shí)間復(fù)雜度是n^3沪么，n為序列的長(zhǎng)度硼婿。
方法2，暴力也可以?xún)?yōu)化一點(diǎn)：
? ? ? ? 在方法一中禽车，對(duì)于i與j中間的每一個(gè)點(diǎn)k寇漫，我們都會(huì)計(jì)算一遍從i到k的所有數(shù)之和，其實(shí)這里我們做了很多次無(wú)用的計(jì)算殉摔，即點(diǎn)i到點(diǎn)k的數(shù)之和州胳，為點(diǎn)i到點(diǎn)k-1的數(shù)之和，加上點(diǎn)k的數(shù)值逸月。同時(shí)栓撞，我們每一個(gè)起點(diǎn)i開(kāi)始的子序列，最長(zhǎng)的結(jié)尾j都一定是在完整序列的最后碗硬，所以這里我們只需要兩層循環(huán)就可以了：
方法3瓤湘，直接暴力但是可靠的線性算法：
????????在講這個(gè)算法前捌归，首先我們需要弄清楚的是最大子序和的這個(gè)子序所包含的一些特性：
*1）.最大子序的開(kāi)始和結(jié)尾兩個(gè)數(shù)一定都是正數(shù)，如果不是岭粤，那么子序列拋棄這個(gè)負(fù)數(shù)惜索，會(huì)變的更大。
*2）.最大子序列中任何一個(gè)包含了第一個(gè)數(shù)的左子序列或者包含了最后一個(gè)數(shù)的右子序列剃浇，其和一定是正數(shù)巾兆，如果不是，那么最大子序列拋棄這一段子序虎囚，會(huì)變得更大角塑。
*3）.最大子序列外左邊第一個(gè)數(shù)開(kāi)始往左任意連續(xù)多個(gè)數(shù)之和以及最大子序列外右邊第一個(gè)數(shù)開(kāi)始任意多個(gè)數(shù)之和，一定都是小于零的淘讥，否則最大子序列可以加上這一段數(shù)變得更大圃伶。
????????由以上三個(gè)特性，我們可以實(shí)現(xiàn)這樣一個(gè)方法：
? ? ? ? 我們從序列的第一個(gè)數(shù)開(kāi)始往后掃描蒲列。如果這個(gè)數(shù)小于零窒朋，那么它一定不會(huì)是最大子序列的第一個(gè)數(shù)，我們就繼續(xù)往后掃描（特性*1）蝗岖。如果這個(gè)數(shù)大于零侥猩，我們認(rèn)為它可能是最大子序列的第一個(gè)數(shù)，我們從這個(gè)數(shù)開(kāi)始求和抵赢，每往后掃到一個(gè)數(shù)欺劳，就把新的數(shù)加到這個(gè)和，只要這個(gè)和還大于零铅鲤，這連續(xù)的子序列就可能是最大子序列的一部分（特性*2）划提。在不斷加數(shù)的過(guò)程中，我們維護(hù)一個(gè)全局的變量邢享，用來(lái)記錄最大子序和鹏往，每次掃描一個(gè)數(shù)，都判斷這個(gè)變量能否更新驼仪。一旦我們?cè)诩拥倪^(guò)程中掸犬，子序和小于零了，那么這之前的所有數(shù)我們都直接拋棄绪爸，因?yàn)橹暗臄?shù)不會(huì)是最大子序列的一部分（特性*3），我們從下一個(gè)數(shù)開(kāi)始計(jì)算新的子序列宙攻。
? ? ? ? 如此操作奠货，是需要我們對(duì)整個(gè)序列從左到右掃描一次，我們就可以在這個(gè)過(guò)程中得到最大子序和座掘。實(shí)現(xiàn)如下：
方法4递惋，狀態(tài)轉(zhuǎn)移柔滔，動(dòng)態(tài)規(guī)劃：
? ? ? ? 方法3中，可以認(rèn)為我們每次都是確定了一個(gè)子序列的第一個(gè)數(shù)萍虽，然后從該數(shù)開(kāi)始計(jì)算之后的子序列睛廊，其實(shí)我們也可以根據(jù)子序列的最后一個(gè)數(shù)來(lái)判斷子序列的和的大小。
? ? ? ? 最大子序列一定是以某一個(gè)序列中的數(shù)為結(jié)尾杉编，這個(gè)數(shù)一定是正數(shù)超全。對(duì)序列中的每個(gè)數(shù)，都有兩種可能：
（1）這個(gè)數(shù)與之前若干數(shù)組成序列邓馒，這個(gè)數(shù)是最后一個(gè)嘶朱。
（2）這個(gè)數(shù)就是單獨(dú)的一個(gè)序列。
? ? ? ? 我們認(rèn)為光酣，在任意一個(gè)位置i疏遏，如果確認(rèn)了i位置上的數(shù)是序列的最后一個(gè)數(shù)，那么這個(gè)序列的和最大應(yīng)該是以i-1為結(jié)尾的序列加上i位置的數(shù)救军，和單獨(dú)只有i這個(gè)位置上的數(shù)财异，兩者中較大的一個(gè)。如果以f[i]記錄以第i個(gè)位置的數(shù)為結(jié)尾的最大子序之和唱遭，具體狀態(tài)轉(zhuǎn)移如下：
????????f[i] = max( f[i-1] + nums[i],? nums[i])
????????如此我們掃描一遍整個(gè)數(shù)組宝当，從第一個(gè)位置到最后一個(gè)位置，每次都已當(dāng)前位置為子序列最后一個(gè)數(shù)胆萧，求得當(dāng)前位置結(jié)束的最大子序列庆揩，同時(shí)更新全局的最大子序和，便能得到最終的最大子序和跌穗。具體實(shí)現(xiàn)如下：
方法5订晌，最優(yōu)美的分治算法：
? ? ? ? 最大子序列只可能有三種情況：在序列的左半部分，在序列的右半部分蚌吸，橫跨序列中間（包含左半部分最后一個(gè)與右半部分第一個(gè)）锈拨。所以我們需要做的就是，對(duì)比著三部分的大小羹唠，然后返回最大的一個(gè)和奕枢。
? ? ? ? 對(duì)于中間部分，求和的辦法是從中間分別求出往左的最大值與往右的最大值佩微，兩邊加起來(lái)即為最大的橫跨兩邊的子序列缝彬。
? ? ? ? 解題絕對(duì)不是把題做出來(lái)、能得到一個(gè)答案就可以哺眯。嘗試不同方法的過(guò)程谷浅，其實(shí)是一個(gè)探索問(wèn)題的根本問(wèn)題的過(guò)程。找到了最根本的核心點(diǎn)，也就能相應(yīng)的得到正確的解法一疯。
? ? ? ? 使用更快的算法來(lái)解題撼玄，不僅僅是為了炫技，更是為了能解決更艱難情況下的問(wèn)題墩邀，讓所有問(wèn)題都變成可解的掌猛。
