輸入一個(gè)整型數(shù)組，數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值。

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

示例

• 輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]

• 輸出: 6

• 解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

提示

• 1 <= arr.length <= 10^5

• -100 <= arr[i] <= 100

方法：動(dòng)態(tài)規(guī)劃

• 狀態(tài)定義：dp[i] 表示以 nums[i] 結(jié)尾的連續(xù)子數(shù)組的最大和；

• 狀態(tài)轉(zhuǎn)移方程：

• 如果 dp[i - 1] > 0， dp[i] = dp[i - 1] + nums[i];

• 如果 dp[i - 1] ≤ 0，dp[i] = nums[i]。

• 初始化：dp[0] = nums[0];

• 輸出：max(dp);

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 為 nums 數(shù)組的長(zhǎng)度。我們只需要遍歷一遍數(shù)組即可求得答案。

• 空間復(fù)雜度：O(1)。我們只需要在常數(shù)空間存放若干變量。

END

勤能補(bǔ)拙是良訓(xùn)，一分耕耘一分才，贈(zèng)友人。

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。