Super-short algorithm to find the maximum subarray.

maximum_subarray.cpp

template<typename Iterator>
auto maximum_subarray(Iterator begin, Iterator end) -> decltype(*begin + *begin)
{
	using T = decltype(*begin + *begin);
	
	T sum = 0;
	
	T best = 0;
	
	auto largest = end;
	
	for ( ; begin != end; ++begin)
	{
		sum += *begin;
		
		if (largest == end || *begin > *largest) largest = begin;
		
		if (sum > best) best = sum;
			
		else if (sum < 0) sum = 0;
	}
	
	// in std::max(largest, best) best (at least 0)
	// would win if largest is negative
	if (*largest < 0) return *largest;
	
	return best;
}