main.cpp

by Jay Kadane。Input:a vector with floats.Output:the maximum submatrix.

//: by Jay Kadane
// 输入是一个具有n个浮点数字的向量x；
// 其输出是在输入的任何相邻子向量中找出的最大和。
# include <iostream.h>
# include <algorithm>
const int n = 10;

template <typename T>
inline T const& max (T const& a, T const& b)
{
    return  a < b  ?  b : a;
}

int main()
{
	//int x[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
	int x[n], i = 0;
	for (i = 0; i < n; ++i)
	{ cin >> x[i]; }
	int maxsofar = 0, maxendinghere = 0;
	int j = 0, k = 0;
	for (i = 0; i < n; ++i)
	{
		// invariant: maxendinghere and maxsofar are accurate for x[0..i-1]
		if ( (maxendinghere + x[i]) <= 0)
		{ j = i + 1; }
		maxendinghere = max(maxendinghere + x[i], 0);
		if (maxendinghere > maxsofar)
		{ k = i; }
		maxsofar = max(maxsofar, maxendinghere);
	}
	cout << j << ", " << k << endl;
	cout << maxsofar << endl;
	return 0;
}
///~