Maximum non-adjacent sum of a list of numbers

MaxSum.cpp

// MaxSum.cpp : Just a silly little problem to solve -- what is the
// maximum sum of non-adjacent numbers in an array?

#include "stdafx.h"

#include <algorithm>
#include <deque>
#include <iostream>
#include <string>
#include <vector>

template <typename T>
void printarray(T& array_to_print)
{
  std::cout << "{";
  for (auto item : array_to_print)
  {
    std::cout << " ";
    std::cout << item;
  }
  std::cout << " } ";
}

template<typename ReturnType>
ReturnType max_subset(std::vector<ReturnType>& items)
{
  size_t index(0);
  // Keep a rolling window of maxima found
  std::deque<ReturnType> subset_sums;

  for (ReturnType item : items)
  {
    ReturnType max_value(0);
    // Greedily find the largest maximum in the window, ignoring the last entry.
    if (index >= 2)
    {
      // subset_sums.end() - 1: All the way up to the next-to-last element
      auto max_iter(std::max_element(subset_sums.begin(), subset_sums.end() - 1));
      max_value = *max_iter;
      if (max_iter != subset_sums.begin())
      {
        subset_sums.erase(subset_sums.begin(), max_iter);
      }
    }
    else
    {
      index++;
    }
    // Add the new greatest maximum in the window
    // The std::max(item, 0) is there to skip over adding negative scores to the max
    subset_sums.push_back(std::max(item, ReturnType(0)) + max_value);
  }

  return *(std::max_element(subset_sums.begin(), subset_sums.end()));
}

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector<int> first_list = {1, 2, 10, 10, 5, 1, 10, 2};
  printarray(first_list);
  auto max_value(max_subset(first_list));
  std::cout << max_value << "\n";

  std::vector<int> second_list = { 1, 1, 1, -1, 1, 1, 2};
  printarray(second_list);
  auto second_max_value = max_subset(second_list);
  std::cout << second_max_value << "\n";

  std::vector<double> third_list = { 5.5, 10.2, 1.0, 1.0, 32.1 };
  printarray(third_list);
  auto third_max_value = max_subset<double>(third_list);
  std::cout << third_max_value << "\n";

  std::vector<unsigned> fourth_list = { 10, 2, 10, 10, 2 };
  printarray(fourth_list);
  auto fourth_max_value = max_subset<unsigned>(fourth_list);
  std::cout << fourth_max_value << "\n";

  return 0;
}