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.
思路解析的很好：
Maximum Subarray -- LeetCode
這是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃的題目，用到的思路我們?cè)趧e的動(dòng)態(tài)規(guī)劃題目中也很常用促绵，以后我們稱(chēng)為”局部最優(yōu)和全局最優(yōu)解法“攒庵。
基本思路是這樣的嘴纺，在每一步，我們維護(hù)兩個(gè)變量浓冒，一個(gè)是全局最優(yōu)栽渴，就是到當(dāng)前元素為止最優(yōu)的解是，一個(gè)是局部最優(yōu)稳懒，就是必須包含當(dāng)前元素的最優(yōu)的解闲擦。接下來(lái)說(shuō)說(shuō)動(dòng)態(tài)規(guī)劃的遞推式（這是動(dòng)態(tài)規(guī)劃最重要的步驟，遞歸式出來(lái)了场梆，基本上代碼框架也就出來(lái)了）墅冷。
假設(shè)我們已知第i步的global[i]（全局最優(yōu)）和local[i]（局部最優(yōu)），那么第i+1步的表達(dá)式是：
local[i+1]=Math.max(A[i], local[i]+A[i])或油，
就是局部最優(yōu)是一定要包含當(dāng)前元素寞忿，所以不然就是上一步的局部最優(yōu)local[i]+當(dāng)前元素A[i]（因?yàn)閘ocal[i]一定包含第i個(gè)元素，所以不違反條件）顶岸，但是如果local[i]是負(fù)的腔彰，那么加上他就不如不需要的，所以不然就是直接用A[i]辖佣；
global[i+1]=Math(local[i+1],global[i])霹抛，
有了當(dāng)前一步的局部最優(yōu)，那么全局最優(yōu)就是當(dāng)前的局部最優(yōu)或者還是原來(lái)的全局最優(yōu)（所有情況都會(huì)被涵蓋進(jìn)來(lái)卷谈，因?yàn)樽顑?yōu)的解如果不包含當(dāng)前元素杯拐，那么前面會(huì)被維護(hù)在全局最優(yōu)里面，如果包含當(dāng)前元素世蔗，那么就是這個(gè)局部最優(yōu)）端逼。
接下來(lái)我們分析一下復(fù)雜度，時(shí)間上只需要掃描一次數(shù)組凸郑，所以時(shí)間復(fù)雜度是O(n)裳食。空間上我們可以看出表達(dá)式中只需要用到上一步local[i]和global[i]就可以得到下一步的結(jié)果芙沥，所以我們?cè)趯?shí)現(xiàn)中可以用一個(gè)變量來(lái)迭代這個(gè)結(jié)果诲祸，不需要是一個(gè)數(shù)組，也就是如程序中實(shí)現(xiàn)的那樣而昨，所以空間復(fù)雜度是兩個(gè)變量（local和global）救氯，即O(2)=O(1)。
Java代碼
public int maxSubArray(int[] A) {
if(A==null || A.length==0)
return 0;
int global = A[0];
int local = A[0];
for(int i=1;i<A.length;i++)
{
local = Math.max(A[i],local+A[i]);
global = Math.max(local,global);
}
return global;
}
Python代碼
def maxSubArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
if not A:
return 0
localSum = globalSum = A[0]
for num in A[1:]:
localSum = max(num, localSum+num)
globalSum = max(localSum, globalSum)
return globalSum
