// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

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

/*
float maxBeneficio(const vector<float> & beneficio, int longitud) {

   // Maximo beneficio que se puede obtener con esa longitud

   float resultado;

   if (longitud == 1)
      resultado = beneficio[1];
   else {
      resultado = beneficio[longitud];
      for (int fragmento = 1; fragmento < longitud; fragmento++)
	 resultado = max(resultado,
			 beneficio[fragmento] + maxBeneficio(beneficio, longitud - fragmento));
   }

   return resultado;

}

float maxBeneficio(const vector<float> & beneficio) {

   return maxBeneficio(beneficio, beneficio.size() - 1);

}
*/

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

/*
#define DESCONOCIDO -1

float maxBeneficio(const vector<float> & beneficio, int longitud, vector<float> & resultado) {

   if (resultado[longitud] == DESCONOCIDO)
      if (longitud == 1)
	 resultado[longitud] = beneficio[1];
      else {
	 resultado[longitud] = beneficio[longitud];
	 for (int fragmento = 1; fragmento < longitud; fragmento++)
	    resultado[longitud] = max(resultado[longitud],
				      beneficio[fragmento] + maxBeneficio(beneficio, longitud - fragmento, resultado));
      }
   
   return resultado[longitud];

}

float maxBeneficio(const vector<float> & beneficio) {

   vector<float> resultado(beneficio.size(), DESCONOCIDO);
   return maxBeneficio(beneficio, beneficio.size() - 1, resultado);

}
*/

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

/*
float maxBeneficio(const vector<float> & beneficio) {

   vector<float> resultado(beneficio.size());

   for (int longitud = 1; longitud < beneficio.size(); longitud++)
      if (longitud == 1)
	 resultado[longitud] = beneficio[1];
      else {
	 resultado[longitud] = beneficio[longitud];
	 for (int fragmento = 1; fragmento < longitud; fragmento++)
	    resultado[longitud] = max(resultado[longitud],
				      beneficio[fragmento] + resultado[longitud - fragmento]);
      }
   
   return resultado[beneficio.size() - 1];

}
*/

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

int main () {

   vector<float> ejemploBeneficio = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 26};

   float resultado = maxBeneficio(ejemploBeneficio);
   cout << "Maximo beneficio: " << resultado << endl;
   if (resultado == 27)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}