題目：
題目鏈接https://leetcode-cn.com/problems/maximum-subarray/description/
背景：
????????本題為非常經(jīng)典的一道算法入門題，有著多種非常高效的解題方法，可以幫助答題感受到“找到問(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，暴力也可以優(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)題都變成可解的。
