leetcode 剑指 Offer 42. 连续子数组的最大和
2020-10-25 本文已影响0人
Source_Chang
1，记录上一次的最大和
C++：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSubArray = nums[0];
int lastSubArray = maxSubArray;
for ( int i = 1; i < nums.size(); ++i ) {
if ( lastSubArray < 0 ) {
lastSubArray = nums[i];
} else {
lastSubArray += nums[i];
}
if ( lastSubArray > maxSubArray ) {
maxSubArray = lastSubArray;
}
}
return maxSubArray;
}
};
2，maxSubArray = sum - minSum
C++：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSubArray = nums[0];
int minSum = min(maxSubArray, 0);
int sum = maxSubArray;
for ( int i = 1; i < nums.size(); ++i ) {
sum += + nums[i];
maxSubArray = max(maxSubArray, sum - minSum);
minSum = min(minSum, sum);
}
return maxSubArray;
}
};
