輸入一個(gè)?非空?整型數(shù)組，數(shù)組里的數(shù)可能為正，也可能為負(fù)。

數(shù)組中一個(gè)或連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組。

求所有子數(shù)組的和的最大值。

要求時(shí)間復(fù)雜度為?O(n)。

數(shù)據(jù)范圍：

數(shù)組長(zhǎng)度?[1,1000]。
數(shù)組內(nèi)元素取值范圍?[?200,200][?200,200]。

樣例：

輸入：

[ 1，-2，3，10，-4，7，2，-5]

輸出：

18?

解題思路：?本題是求子數(shù)組的最大值。

對(duì)于數(shù)組 [1，......，x，......... ，2]。用 變量s 記錄 x 前一個(gè)子數(shù)組的值，若 s <?0 , x + s, 反而比 x 本身小，那么不如從 x 開始重新設(shè)立一個(gè)新的子數(shù)組。對(duì)于 s > 0 ,?s + x 一定要比 x 大，所以不如將 x 納入 子數(shù)組 s 內(nèi)?（不必?fù)?dān)心 x 小于0，使新子數(shù)組值變小，因?yàn)閞es變量時(shí)刻在更新最大值）。對(duì)于 s = 0 的情況完全可以歸納到 s < 0 內(nèi)。

理論成立代碼如下：

class Solution {public int maxSubArray(int[] nums) {int res = -201;int s = 0;for(int x : nums){if(s < 0)s = 0;s = s + x;res = Math.max(res,s);}return res;}
}

?

?