// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 ***************************************************************************/

/*
float maximoValorRobable(const vector<float> &  valoresCasas,
		         int casa) {

   // Maximo valor acumulable eligiendo que casas robar entre la casa 0 y esa casa

   float resultado;

   if (casa == 0)
      resultado = valoresCasas[0];
   else if (casa == 1)
      resultado = max(valoresCasas[0], valoresCasas[1]);
   else
      resultado = max(valoresCasas[casa] + maximoValorRobable(valoresCasas, casa - 2),
                      maximoValorRobable(valoresCasas, casa - 1));

   return resultado;

}

float maximoValorRobable(const vector<float> & valoresCasas) {
  
   int ultimaCasa = valoresCasas.size() - 1;
   return maximoValorRobable(valoresCasas, ultimaCasa);

}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
#define DESCONOCIDO -1

float maximoValorRobable(const vector<float> &  valoresCasas,
			 int casa,
		         vector<float> & resultado) {

   if(resultado[casa] == DESCONOCIDO)
      if (casa == 0)
	 resultado[casa] = valoresCasas[0];
      else if (casa == 1)
	 resultado[casa] = max(valoresCasas[0], valoresCasas[1]);
      else
	 resultado[casa] = max(valoresCasas[casa] + maximoValorRobable(valoresCasas, casa - 2, resultado),
                               maximoValorRobable(valoresCasas, casa - 1, resultado));

   return resultado[casa];

}

float maximoValorRobable(const vector<float> & valoresCasas) {
  
   int ultimaCasa = valoresCasas.size() - 1;

   vector<float> resultado(ultimaCasa + 1, DESCONOCIDO);

   return maximoValorRobable(valoresCasas, ultimaCasa, resultado);

}
*/

/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
float maximoValorRobable(const vector<float> & valoresCasas) {

   int ultimaCasa = valoresCasas.size() - 1;

   vector<float> resultado(ultimaCasa + 1);

   for (int casa = 0; casa <= ultimaCasa; casa++)
      if (casa == 0) 
	 resultado[casa] = valoresCasas[casa];
      else if (casa == 1)
	 resultado[casa] = max(valoresCasas[0], valoresCasas[1]);
      else
	 resultado[casa] = max(valoresCasas[casa] + resultado[casa - 2],
                               resultado[casa - 1]);

   return resultado[ultimaCasa];

}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/

int main () {

   vector<float> calleMayor = {6000, 10000, 3000, 15000, 4000, 2000, 8000, 5000};
   vector<float> calleAlta = {3000, 6000, 7000, 5000};

   float resultado = maximoValorRobable(calleAlta);
   cout << "Maximo valor robable en calle Alta: " << resultado << endl;
   if (resultado == 11000)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;
	 
   resultado = maximoValorRobable(calleMayor);
   cout << "Maximo valor robable en calle Mayor: " << resultado << endl;
   if (resultado == 33000)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}