? 劍指 Offer 42. 連續(xù)子數(shù)組的最大和
難度：簡(jiǎn)單
輸入一個(gè)整型數(shù)組，數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值。
要求時(shí)間復(fù)雜度為 O(n)。
示例1:
輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
提示：
- 1 < = a r r . l e n g t h < = 1 0 5 1 <= arr.length <= 10^5 1<=arr.length<=105
- $-100 <= arr[i] <= 100
注意：本題與 53. 最大子數(shù)組和 相同。
??思路：動(dòng)態(tài)規(guī)劃
定義 dp 數(shù)組， dp[i]代表以元素 nums[i] 為結(jié)尾的連續(xù)子數(shù)組最大和。
- 若
dp[i?1] < 0，說(shuō)明dp[i?1]對(duì)dp[i]產(chǎn)生負(fù)貢獻(xiàn)，即dp[i?1]+nums[i]還不如nums[i]本身大。- 當(dāng)
dp[i?1]>=0時(shí)，執(zhí)行：
d p [ i ] = d p [ i ? 1 ] + n u m s [ i ] dp[i]=dp[i?1]+nums[i] dp[i]=dp[i?1]+nums[i] - 當(dāng)
dp[i?1]<0時(shí)，執(zhí)行 ：
d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i]
- 當(dāng)
- 初始狀態(tài)：
dp[0]=nums[0]，即以nums[0]結(jié)尾的連續(xù)子數(shù)組最大和為nums[0]。
優(yōu)化：
- 觀察發(fā)現(xiàn)
dp[i]只與dp[i?1]和nums[i]有關(guān)系，因此可以第一個(gè)變量sum存儲(chǔ)dp[i]的值，即存儲(chǔ)以元素nums[i]為結(jié)尾的連續(xù)子數(shù)組最大和。 - 由于省去
dp列表使用的額外空間，因此空間復(fù)雜度從 O ( n ) O(n) O(n) 降至 O ( 1 ) O(1) O(1)。
??代碼：(C++、Java)
C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int sum = 0;
for(int num : nums){
sum = sum < 0 ? num : sum + num;
ans = max(ans, sum);
}
return ans;
}
};
Java
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num : nums){
sum = sum < 0 ? num : sum + num;
ans = Math.max(ans, sum);
}
return ans;
}
}
?? 運(yùn)行結(jié)果：
?? 復(fù)雜度分析：
-
時(shí)間復(fù)雜度：
O
(
n
)
O(n)
O(n)，其中
n為數(shù)組nums的長(zhǎng)度，我們只需要遍歷一遍數(shù)組即可求得答案。 - 空間復(fù)雜度： O ( 1 ) O(1) O(1)，我們只需要常數(shù)空間存放若干變量。
題目來(lái)源：力扣。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-675834.html
放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁(yè) / CSDN—力扣專欄，每日更新！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-675834.html
注： 如有不足，歡迎指正！
到了這里，關(guān)于(動(dòng)態(tài)規(guī)劃) 劍指 Offer 42. 連續(xù)子數(shù)組的最大和 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
