题目描述 [最大子序和]
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
解题思路
- 令temp为当前最大数组的和,num_max为最后返回的最大数组和
- 从前往后扫描,对于第i个元素有两种选择:加入前面找到的子数组,作为新数组的第一个元素
- 如果temp+a[i] > a[i],则令temp=temp+a[i];
- 否则为temp重新赋值,temp=a[i];
- 比较当前最大数值和与最大数组和
即:
temp = max(temp+a[i], a[i]);
num_max = max(num_max, temp);
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int temp = 0;
int num_max = INT_MIN;
for(auto num:nums){
temp = max(num, temp+num);
num_max = max(num_max, temp);
}
return num_max;
}
};