C++版 - 剑指offer 面试题31：连续子数组的最大和 题解

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
	if(array.size()==0) return 0;  // 输入向量的元素为空，输入无效
	int maxSum = -1<<31; // int maxSum = INT_MIN;   用来保存最大和，初始化为最小的负整数，剑指offer原书上用的16进制带符号的0x80000000表示最小的负整数，不易理解，C++中有相应的常量INT_MIN
	int currentSum = 0;
	for(int i=0;i<array.size();i++)
	{
		currentSum += array[i];
		if(currentSum > maxSum)
			maxSum = currentSum; // 将最大和更新为当前和
		if(currentSum < 0)
			currentSum = 0;
	}
	return maxSum;
    }
};
// 以下为测试部分 
/* 
int main()
{
	vector<int> vec={2,-3,5,-6,10,20};  // vector<int> vec={}; 向量直接赋值的方法C++11标准支持，编译器如果比较旧需要先写数组或迭代器，然后以相关元素创建数组 
	Solution sol;
	cout<<sol.FindGreatestSumOfSubArray(vec)<<endl;
	return 0;
}
*/