2

tengo una duda sobre una función recursiva, esta función dado un vector de enteros aleatorios, por ejemplo [25,6,14,12,20], si compramos acciones el dia 1 (valor 6) y vendemos el dia 4 (valor 20) obtenemos el máximo beneficio. Con lo que esta función nos calcula los dias en los que tendremos una inversión máxima.

Para ello he hecho una función recursiva que calcula la mayor inversión en la mitad de la izquierda, la mitad de la derecha y luego coge el mínimo valor por la izquierda y el máximo por la derecha y coge el mas grande de los 3.

La inversión total me la hace bien, me calcula bien los días cuando el máximo valor de los 3 valores antes comentados es el de la diferencia entre el minimo y el maximo, ahora, en los demás casos los dias nosé como calcularlos, lo he intentado todo.

Os dejo el código de mi función:

int inversion_optimaDyV(const int t[], int izda, int dcha, int &resultado, int n, int &inv, int &ret)
{
  int medio, inversionIzda, inversionDcha;
  int inversion;
  int pos_i, pos_j;
  if (izda == dcha)
  {
    return 0;
  }
  else
  {
    medio = (dcha + izda) / 2;
    medio_1 = medio+1;

    inversionIzda = inversion_optimaDyV(t, izda, medio, resultado, n, inv, ret);
    inversionDcha = inversion_optimaDyV(t, medio+1, dcha, resultado, n, inv, ret);

    if (izda+1 == dcha && dcha < n)
    {
      inversion = t[dcha] - t[izda];
      return inversion;
    }

  }

  int i,j;
  int minimo = t[izda];
  //Buscar el minimo en la parte izda

  if (izda < 0 ) izda = izda +1;

  for (i = izda; i <= medio; ++i)
  {
    if (t[i] < minimo)
    {
      minimo = t[i];
      pos_i = i;
    }
  }

  int maximo = 0;
  //Buscar el maximo en la parte dcha
  if (dcha == n) dcha = dcha -1;

  for (j = medio+1; j <= dcha; ++j)
  {
    if (t[j] > maximo)
    {
      maximo = t[j];
      pos_j = j;
    }
  }
  int diferencia = maximo - minimo;

  if (diferencia >= inversionIzda &&  diferencia >= inversionDcha)
  {
    resultado =  diferencia;
  }
  else if (inversionIzda >= diferencia && inversionIzda >= inversionDcha)
  {
    resultado = inversionIzda;
  }
  else 
  {
    resultado = inversionDcha;
  }
  inv = pos_i;
  ret = pos_j;
  return resultado;
}

2 respuestas 2

2

Tu planteamiento resulta incorrecto y se pueden tirar tus dos hipótesis facilmente:

  1. Se debe comparar el menor con el mayor:
  2. El número más bajo debe encontrarse en la mitad izquierda y el más alto en la mitad derecha

Si atendemos a esta secuencia:

 [7,17,1,5,5,5]

Es fácil verificar en este caso que el máximo beneficio se obtiene con los dos números más altos y que además ambos se encuentran en la mitad izquierda. Tu algoritmo difícilmente va a cubrir todos los casos de uso.

Una aproximación seria iterar por todos los números, excepto el último y, eligiendo para cada uno de ellos como día de compra, calcular todos los posibles beneficios y eligiendo el mayor de ellos.

Una posible solución al problema:

std::pair<int*,int*> findMaxProfit(int * start, int * end, int * iter = nullptr)
{
  if( iter == nullptr ) iter = start+1;

  std::pair<int*,int*> toReturn;
  int maxProfit = 0;

  if( iter != end )
  {
    toReturn = {start,iter};
    maxProfit = *iter - *start;

    std::pair<int*,int*> anotherResult = findMaxProfit(start,end,iter+1);

    if( anotherResult.first != nullptr )
    {
      int const anotherProfit = *anotherResult.second - *anotherResult.first;
      if( maxProfit < anotherProfit )
      {
        maxProfit = anotherProfit;
        toReturn = anotherResult;
      }
    }
  }

  if( start+1 != end )
  {
    std::pair<int*,int*> anotherResult = findMaxProfit(start+1,end,nullptr);

    if( anotherResult.first != nullptr )
    {
      int const anotherProfit = *anotherResult.second - *anotherResult.first;
      if( maxProfit < anotherProfit )
      {
        maxProfit = anotherProfit;
        toReturn = anotherResult;
      }
    }
  }

  return toReturn;
}

Puedes verlo funcionando aqui

2

Creo que lo estás enfocando mal. Según los datos que indicas, no tienes garantías de que los valores de la mitad izquierda de tu formación sean inferiores a los valores de tu mitad derecha.

Una solución no recursiva (no indicas que sea un requisito) es comparar iterativamente todos los valores entre si; una comparación cruzada. El objetivo es encontrar el máximo benefício: aquellas 2 posiciones en la formación ( p1 y p2 ) tal que el resultado de restar p2 - p1 sea mayor al resultado de restar cualesquiera otras 2 posiciones distintas.

Es decir, a partir de tus datos iniciales:

25 6 14 12 20

Generamos una tabla con el resultado de las restas, para cada posible valor con todos los demas, con la condición de que se encuentren mas a la derecha:

    | 25  6  14  12 20
 ---+------------------
 25 | 0 -19 -11 -13 -5
  6 | -   0   8   6 14
 14 | -   -   0  -2  6
 12 | -   -   -   0  8
 20 | -   -   -   -  0

En esta tabla, ya se aprecia claramente que el máximo valor es 14, que corresponde a la resta de los valores en las posiciones 4, 1.

Observa que no es necesario generar la tabla, nos basta con almacenar la posición del mayor beneficio que vayamos encontrando.

Con ese planteamiento, la solución es muy fácil ... aunque, como digo, no es recursiva:

#include <utility>
#include <iostream>

std::pair< int , int > findMaxProfit( const int *start, const int *end ) {
  std::pair< const int *, const int * > sub;
  int max = 0;

  for( auto l1 = start; l1 != end; ++l1 ) {
    for( auto l2 = l1; l2 != end; ++l2 ) {
      auto tmp = ( *l2 ) - ( *l1 );
      if( tmp > max ) {
        max = tmp;
        sub = std::make_pair( l1, l2 );
      }
    }
  }

  return std::make_pair( std::distance( start, sub.first ), std::distance( start, sub.second ) );
}

int main( ) {
  int test[] = { 25,6,14,12,20 };
  auto result = findMaxProfit( std::begin( test ), std::end( test ) );

  std::cout << "minimo: posicion " << result.first << ", valor " << test[result.first];
  std::cout << "\nmaximo: posicion "<< result.second << ", valor " << test[result.second] << '\n';

  return 0;
}

minimo: posicion 1, valor 6
maximo: posicion 4, valor 20

Nota: Puedes ver el código funcionando en Wandbox.

El método es susceptible de optimizaciones. Todas las operaciones que restan un número consigo mismo son inútiles ... lo dejo al aburrimiento de cada uno :-)

2
  • Gracias por responder, ya he encontrado la solución a mi problema, era cosa de los return, y si era necesario hacerlo recursivo ya que la eficiencia de un for anidado es de O(n^2) mientras que la recursiva dividiendo por la mitad sale O(n logn). el 29 mar. 2019 a las 9:10
  • Me alegra que lo resolvieras, pero esos cálculos tuyos de eficiencia son incorrectos. Sería así si los 2 for recorrieran toda la tabla, pero no es así, el segundo solo recorre algunos elementos. Y te ahorras los call, que tienen un coste significativo ... sería interesante una comparativa :-)
    – Trauma
    el 29 mar. 2019 a las 9:20

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.