O(n) solution to the maximum subarray sum problem using Kadane's algorithm

kadane.cpp

#include <tuple>
#include <iterator>
#include <algorithm>

template <class InputIterator>
std::tuple<typename std::iterator_traits<InputIterator>::value_type,
           InputIterator, InputIterator>
maximum_subarray(InputIterator first, InputIterator last) {
  typedef typename std::iterator_traits<InputIterator>::value_type value_type;
  using std::max;

  value_type max_ending_here(0), max_so_far(0);
  InputIterator max_start, max_end;
  max_start = max_end = first;
  while (first != last) {
    if (*first < max_ending_here + *first)
      max_ending_here += *first;
    else {
      max_ending_here = *first;
      max_start = first;
    }
    if (max_so_far < max_ending_here) {
      max_so_far = max_ending_here;
      max_end = first + 1;
    }
    ++first;
  }

  return std::make_tuple(max_so_far, max_start, max_end);
}