給定一個(gè)整數(shù)數(shù)組 nums 时肿，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）淆游，返回其最大和夭谤。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大桶良，為 6。
代碼：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size() == 0) return 0;
int *dp = new int[nums.size()];
dp[0] = nums[0];
int sum = nums[0];
for(int i = 1; i < nums.size(); ++i) {
if(sum < 0) {
dp[i] = nums[i] > dp[i - 1] ? nums[i] : dp[i - 1];
sum = nums[i];
} else {
dp[i] = nums[i] + sum > dp[i - 1] ? nums[i] + sum : dp[i - 1];
sum += nums[i];
}
}
return dp[nums.size() - 1];
}
};
// 只需要兩者狀態(tài)沮翔，進(jìn)行優(yōu)化
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int last = nums[0], cur;
int max = last;
for (int i = 1; i < nums.size(); ++i) {
cur = last > 0 ? last + nums[i] : nums[i];
max = max < cur ? cur : max;
last = cur;
}
return max;
}
};
