數組連續子數組的最大和

問題的輸入是具有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;
}