数组连续子数组的最大和

问题的输入是具有n个浮点数的向量x，输出是输入向量的任何连续子向量中的最大和

总体思想来源于编程珠玑第二版第八章

#include <iostream>
#include <algorithm>
using namespace std;
const int n = 10;
//此乃解决输入连续子向量中的最大和的效率最高的一种算法，动态规划法；当所有的输入都是负数时，总和
//最大的子向量是空向量，总和为0
//关键理解：maxendinghere
int main()
{
	int arr[n] = {31,-41,59,26,-53,58,97,-93,-23,84};
	int maxsofar = 0;
	int maxendinghere = 0;
	for (int i = 0; i < n; ++i) {
		//maxendinghere是结束位置为i-1的最大子向量的和，若加上x[i]之后的结果依然为
		//正值，则该赋值语句将maxendinghere增大x[i];若加上x[i]之后的结果为负值，则将
		//maxendinghere重新设为0
		maxendinghere = max(maxendinghere+arr[i], 0);
		maxsofar = max(maxendinghere, maxsofar);
	}
	cout << maxsofar << endl;
	int a;
	cin >> a;
}