1、題目描述
輸入一個(gè) 非空 整型數(shù)組罗晕，數(shù)組里的數(shù)可能為正济欢，也可能為負(fù)。
數(shù)組中一個(gè)或連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組小渊。
求所有子數(shù)組的和的最大值法褥。
要求時(shí)間復(fù)雜度為O(n)。
樣例
輸入：[1, -2, 3, 10, -4, 7, 2, -5]
輸出：18
2酬屉、問題描述：
3半等、問題關(guān)鍵：
- 連續(xù)子數(shù)組。
- 最大后綴和呐萨。
- dp[i] = max(0, dp[i - 1]) + nums[i];
4杀饵、C++代碼：
算法 1:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max = -100000;
int sum = 0;
for (int i = 0; i < nums.size(); i++){
if (sum < 0) {
sum = nums[i];
}else
sum += nums[i];
if(max < sum) max = sum;
}
return max;
}
};
算法2:（dp）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int dp[n];
dp[0] = nums[0];
int res = nums[0];
for (int i = 1; i < n; i ++) {
dp[i] = max(0, dp[i - 1]) + nums[i];
res = max(res, dp[i]);
}
return res;
}
};
