- 遍历每个数,计算以当前数为子数组尾元素时的最大和。当上次的和为负数时,则从当前数开始重新计算和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN;
int sum = 0;
for (auto& x : nums) {
if (sum >= 0) {
sum += x;
} else {
sum = x;
}
res = max(res, sum);
}
return res;
}
};
- 动态规划,
dp[i]
表示以 nums[i]
为子数组尾元素时的最大和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (empty(nums)) {
return 0;
}
vector<int> dp(size(nums));
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < size(dp); ++i) {
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
res = max(res, dp[i]);
}
return res;
}
};