2.6　最大子序列和

題目描述（第53題）

求數(shù)組中最大連續(xù)子序列和，例如，給定數(shù)組A=[1,3,-2,4,-5]，則最大連續(xù)子序列和為6，即1+3+（-2）+4=6。

首先明確一下題意。

●　題目說的子數(shù)組是連續(xù)的。

●　題目只需要求和，不需要返回子數(shù)組的具體位置。

●　數(shù)組中的元素是整數(shù)，可能是正數(shù)、負(fù)數(shù)和0。

●　子序列的最小長度為1。

比如：

●　對(duì)于數(shù)組[1,-2,3,5,-3,2]，應(yīng)該返回3+5=8。

●　對(duì)于數(shù)組[0,-2,3,5,-1,2]，應(yīng)該返回3+5+(-1)+2=9。

●　對(duì)于數(shù)組[-9,-2,-3,-5,-3]，應(yīng)該返回-2。

解法一　暴力法（超時(shí)）

一般情況下，可以先用暴力法進(jìn)行分析，再一步步進(jìn)行優(yōu)化。

思路

首先來試一下最直接的方法，就是計(jì)算所有的子序列和，然后取出最大值。定義 Sum[i,…,j]為數(shù)組A中第i個(gè)元素到第j個(gè)元素的和，其中0≤i≤j < n，遍歷所有可能的Sum[i,…,j]即可。

代碼

復(fù)雜度分析

●　時(shí)間復(fù)雜度：O(n2)，其中n為數(shù)組長度。

●　空間復(fù)雜度：O(1)。

解法二　分治法

解法一的空間復(fù)雜度非常理想，但是時(shí)間復(fù)雜度有點(diǎn)高，該怎么優(yōu)化呢？

思路

這道題實(shí)際上是一個(gè)可以用多種方法解決的題目，如果你想到了上面的解法，我想面試官肯定不會(huì)滿意，而如果你一時(shí)想不到更好的解決方法的話，有兩種方法可以幫助你厘清思路。

1.舉幾個(gè)簡單的例子。這種方法通常適用于很復(fù)雜的問題，人們一時(shí)間難以發(fā)現(xiàn)其中的規(guī)律。樹和鏈表等題目使用這種方法比較好，搭配畫圖來將問題進(jìn)行可視化的展現(xiàn)效果會(huì)更好。

2.將大問題拆解為若干子問題，通過解決子問題，以及探尋子問題和大問題之間的關(guān)系來解決。

這里我們采用第2種方法。

假如先把數(shù)組平均分成左、右兩部分，那么此時(shí)有3種情況。

●　最大子序列全部在數(shù)組左部分，不妨用left表示。

●　最大子序列全部在數(shù)組右部分，不妨用right表示。

●　最大子序列橫跨數(shù)組左右部分，不妨用crossMaxSum表示。

對(duì)于前兩種情況，相當(dāng)于將原問題轉(zhuǎn)化成了規(guī)模更小的同類問題。對(duì)于第3種情況，由于已知循環(huán)的起點(diǎn)（即中點(diǎn)），只需要向左、向右分別找出左邊和右邊的最大子序列，那么當(dāng)前最大子序列就是向左能夠達(dá)到的最大子序列+nums[mid]+向右能夠達(dá)到的最大子序列。因此，一個(gè)思路就是每次都將數(shù)組分成左、右兩部分，然后分別計(jì)算上面這3種情況的最大子序列和，最后返回最大值即可。

代碼

復(fù)雜度分析

●　時(shí)間復(fù)雜度：從上圖可以看出每層的節(jié)點(diǎn)在[n,2n]之間，且一共有 logn層，因此時(shí)間復(fù)雜度為O(nlogn)，其中n為數(shù)組長度。

●　空間復(fù)雜度：空間復(fù)雜度取決于函數(shù)調(diào)用棧的深度，故空間復(fù)雜度為O(logn)，其中n為數(shù)組長度，這也可以從上圖直觀地感受到。

解法三　動(dòng)態(tài)規(guī)劃

思路

我們重新思考一下這個(gè)問題，觀察能否將其拆解為規(guī)模更小的問題，并找出遞推關(guān)系來解決？

不妨假設(shè)問題Q(list,i)表示list中以索引i結(jié)尾的最大子序列和，那么原問題就轉(zhuǎn)化為Q(list,i)中的最大值，其中i =0,1,2,…,n-1。

繼續(xù)來看一下Q(list,i)和Q(list,i-1)的關(guān)系，即如何根據(jù)Q(list,i-1)推導(dǎo)出Q(list,i)。

1.如果Q(list,i-1)>0，則表示以索引i-1結(jié)尾的最大子序列和大于0，因此nums[i]一定要和Q(list,i-1)部分結(jié)合，這樣才能使結(jié)果更優(yōu)，即Q(list,i)=Q(list, i-1)＋nums[i]，這是一種貪心的思想。

2.如果Q(list,i-1)≤0，則為了使結(jié)果更優(yōu)，nums[i]應(yīng)該不與Q(list,i-1)相加。

分析到這里，遞推關(guān)系就很明朗了，即Q(list,i)=max(0,Q(list,i-1))+nums[i]。

代碼

復(fù)雜度分析

●　時(shí)間復(fù)雜度：O(n)，其中n為數(shù)組長度。

●　空間復(fù)雜度：O(1)。

解法四　前綴和

思路

下面從數(shù)學(xué)分析的角度來看一下這個(gè)題目。定義函數(shù)S(i)，它的功能是計(jì)算從0（包括0）開始加到i（包括i）的值，即S(i)=list[0]+list[1]+…+list[i]。那么S(j)-S(i-1)就等于從i開始（包括i）加到j（包括j）的值，這在數(shù)學(xué)上被稱為前綴和求差，因此實(shí)際上只需要遍歷一次計(jì)算出所有的S(i)，其中i等于0,1,2,…,n-1，然后利用前綴和就可以計(jì)算出任意區(qū)間的和。這種算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

其實(shí)很多題目都有這樣的思想，比如每日一題——電梯問題（見參考鏈接/正文[1]）。甚至可以將此方法擴(kuò)展到二維空間，即對(duì)二維空間計(jì)算前綴和，利用前綴和的技巧計(jì)算任意矩陣區(qū)域的和，由于篇幅原因，這里就不展開講解了。

代碼

復(fù)雜度分析

●　時(shí)間復(fù)雜度：O(n)，其中n為數(shù)組長度。

●　空間復(fù)雜度：O(1)。

小結(jié)

我們使用了4種方法來解決最大子序列和問題，并詳細(xì)分析了各個(gè)解法的思路及復(fù)雜度。即使你無法通過數(shù)學(xué)方法解決，通過分治法或動(dòng)態(tài)規(guī)劃解決也是可以的。相信下次你碰到相同或類似的問題時(shí)也能夠發(fā)散思維，做到一題多解、多題一解。

這里只是求出了最大的和，如果題目進(jìn)一步要求求出最大子序列和的子序列呢？如果題目允許不連續(xù)呢？又該如何思考和變通？如果將數(shù)組改成二維的，求解最大矩陣和該怎么計(jì)算？這些問題就留給讀者自己思考了。