題目：

輸入一個整型數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。數(shù)組中的一個或連續(xù)多個整數(shù)組成一個子數(shù)組，求所有子數(shù)組的和的最大值。要求時間復雜度為O(n)。

例如，輸入的數(shù)組為{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子數(shù)組為{3, 10, -4, 7, 2}，因此輸出為該子數(shù)組的和18。

最直觀的解法，即枚舉數(shù)組的所有子數(shù)組并求出它們的和。一個長度為n的數(shù)組，總共有n(n+1)/2個子數(shù)組。計算出所有子數(shù)組的和，最快也需要O(n2)時間。

思路一：舉例分析數(shù)組的規(guī)律

我們試著從頭到尾逐個累加示例數(shù)組中的每個數(shù)字。初始化和為0.第一步加上第一個數(shù)字1，此時和為1。第二步加上數(shù)字-2，和就變成了-1。第三步加上數(shù)字3。我們注意到由于此前累加的和是-1，小于0，那如果用-1加上3，得到的和是2，比3本身還小。也就是說，從第一個數(shù)字開始的子數(shù)組的和會小于從第三個數(shù)字開始的子數(shù)組的和。因此，我們不用考慮從第一個數(shù)字開始的子數(shù)組，之前累加的和也被拋棄。

我們從第三個數(shù)字重新開始累加，此時得到的和是3。第四步加10，得到的和為13。第五步加上-4，和為9。我們發(fā)現(xiàn)，由于-4是一個負數(shù)，因此累加-4之后得到的和比原來的和還要小。因此，我們要把之前得到的和13保存下來，因為它有可能是最大的子數(shù)組的和。第六步加上數(shù)字7，9加7的結(jié)果是16，此時的和比之前最大的和13還要大，把最大的子數(shù)組的和由13更新為16。第七步加上2，累加得到的和為18，同時更新最大子數(shù)組的和。第八步加上最后一個數(shù)字-5，由于得到的和為13，小于此前最大的和18，因此，最終最大的子數(shù)組的和為18，對應的子數(shù)組是{3, 10, -4, 7, 2}。具體過程如下：

思路二：應用動態(tài)規(guī)劃法

如果算法的功底足夠扎實，那么我們還可以用動態(tài)規(guī)劃的思想來分析這個問題。如果用函數(shù)f(i)表示以第i個數(shù)字結(jié)尾的子數(shù)組的最大和，那么我們需要求出max[f(i)]，其中0<=i<n。我們可以用如下遞歸公式求f(i)：

這個公式的意義：當以第i-1個數(shù)字結(jié)尾的子數(shù)組中所有數(shù)字的和小于0時，如果把這個負數(shù)與第i個數(shù)累加，則得到的結(jié)果比第i個數(shù)字本身還要小，所以這種情況下以第i個數(shù)字結(jié)尾的子數(shù)組就是第i個數(shù)字本身。如果以第i-1個數(shù)字結(jié)尾的子數(shù)組中所有數(shù)字的和大于0，則與第i個數(shù)字累加就得到以第i個數(shù)字結(jié)尾的子數(shù)組中所有數(shù)字的和。

python代碼如下：

def FindGreatestSumOfSub(nums):
    if not nums:
        return 0
    
    sum =0
    res =nums[0]
    for i in range(len(nums)):
        if sum <=0:
            sum =nums[i]
        else:
            sum +=nums[i]
            
        if sum >res:
            res =sum
            
    return res

更多精彩，關注“咋家”