algorithm - Maximizando los beneficios para cotizaciones accionarias dadas

recursion dynamic-programming

Question

Me hicieron esta pregunta durante una entrevista para una startup y volví a ver esto en el concurso reciente en

Code Sprint: sistemas

**La pregunta :

Le dan los precios de las acciones por un conjunto de días. Cada día, puede comprar una unidad de stock, vender cualquier cantidad de unidades de stock que ya haya comprado o no hacer nada. ¿Cuál es la ganancia máxima que puede obtener al planificar su estrategia comercial de manera óptima? **

Ejemplos (la entrada, es decir, el número de días puede variar)

5 3 2 => beneficio = 0 // dado que el precio disminuye cada día, el máximo beneficio que podemos obtener = 0

1 2 100 => ganancia = 197

1 3 1 2 => ganancia = 3 // compramos a 1 venta a 3, luego compramos a 1 y vendemos a 2 .. ganancia total = 3

Mi solución :

a) Encuentre el día en que el precio de las acciones fue mayor. Sigue comprando 1 unidad de acciones hasta ese día.

b) Si ese día es el último día, abandone:

else: venda todas las existencias en ese día y divida la matriz después de ese día y recurse en los elementos restantes
c) fusionar los beneficios

por ejemplo, 1 4 1 2 3
a) el precio más alto de las acciones el día 2 ... entonces compramos acciones el día 1 y las vendemos el día 2 (ganancia = 3) luego recurrimos en los días restantes: 1 2 3

b) El precio máximo es 3 (en el día 5) así que seguimos comprando acciones el día 3 y el día 4 y vendemos el día 5 (ganancia = (3 * 2 - 3 = 3)

c) Beneficio total = 3 + 3 = 6

La complejidad para esto resulta ser O (n ^ 2). esta solución pasó 10 de los 11 casos, pero excedió el límite de tiempo en un último caso de prueba (es decir, la entrada más grande)

Entonces mi pregunta es si alguien puede pensar en una solución más eficiente para este problema? ¿Hay una solución de programación dinámica?

PD: esta es la primera vez que hago una pregunta aquí. así que por favor avíseme si necesito mejorar / agregar cosas a esta pregunta

Answer 1

Acabo de resolver ese problema en un sitio de concurso. Creo que obtuve un algoritmo más simple que la respuesta aceptada.

1. smax = maximum stock price from the list
2. then find the profit by assuming you have bought all the stocks till smax 
   and you sell it at the price of smax
3. then check if smax is the last element of the stock price list 
   if yes then return profit as answer, 
   if no 
   then make a new list containing stock prices after smax to the last stock price
   and repeat steps 1-3 and keep adding profit of each iteration to get the final profit.

Answer 2

Estoy de acuerdo con la lógica de su método, pero no es necesario realizar un procesamiento recursivo o búsquedas globales máximas. Para encontrar los días de venta / compra, solo tiene que mirar cada día una vez:

El truco es comenzar desde el final. ¡El comercio de acciones es fácil si su viaje retrocede en el tiempo!

Si crees que el código es más fácil de leer que las palabras, simplemente omita mi explicación, pero aquí va:

Leyendo desde el final, mira el precio de ese día. ¿Es este el precio más alto hasta el momento (desde el final), luego se vende! El último día (donde comenzamos a leer) siempre venderás.

Luego vaya al día siguiente (recuerde, al revés en el tiempo). ¿Es el precio más alto hasta ahora (de todos los que hemos visto hasta ahora)? - Entonces vende todo, no encontrarás un día mejor. De lo contrario, los precios aumentan, así que compre. continuar de la misma manera hasta el comienzo.

Todo el problema se resuelve con un solo ciclo inverso : calculando tanto las decisiones como el beneficio del intercambio.

Aquí está el código en python tipo C: (evité la mayoría de las cosas pitónicas. Debe ser legible para una persona C)

def calcprofit(stockvalues): 
    dobuy=[1]*len(stockvalues) # 1 for buy, 0 for sell
    prof=0
    m=0
    for i in reversed(range(len(stockvalues))):
        ai=stockvalues[i] # shorthand name
        if m<=ai:
            dobuy[i]=0
            m=ai
        prof+=m-ai
    return (prof,dobuy)  

Ejemplos:

calcprofit([1,3,1,2]) gives (3, [1, 0, 1, 0])
calcprofit([1,2,100]) gives (197, [1, 1, 0])
calcprofit([5,3,2])   gives (0, [0, 0, 0])
calcprofit([31,312,3,35,33,3,44,123,126,2,4,1]) gives
 (798, [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0])

Tenga en cuenta que m es el precio de las acciones más alto que hemos visto (desde el final). Si ai==m , la ganancia de las acciones compradas en el paso es 0: tuvimos un precio decreciente o estable después de ese punto y no compramos.

Puede verificar que el cálculo del beneficio sea correcto con un simple bucle (para simplificar, imagine que está dentro de la función anterior)

stock=0
money=0
for i in range(len(stockvalues)):  
    if dobuy[i]:
        stock+=1
        money-=stockvalues[i]
    else:
        money+=stockvalues[i]*stock
        stock=0
print("profit was: ",money)

Answer 3

Mi razonamiento es que obtiene ganancias por cada acción comprada antes del precio máximo de las acciones. Usando esta línea de pensamiento, usted compra todas las acciones antes del precio máximo, lo vende al máximo y repite lo mismo con los precios de las acciones restantes.

function profit(prices){
    var totalStocks = 0, profitMade = 0;

    var buySell = function(sortedPrices){
        for(var i = 0, len = sortedPrices.length; i < len; i++){
            if (i < len - 1){
                totalStocks++;
                profitMade = profitMade - sortedPrices[i];
            }else{
                profitMade = profitMade + totalStocks * sortedPrices[i];
                totalStocks = 0;
            }
        }
    }, splitMaxPrice = function(rawPrices){
        var leftStocks = rawPrices.splice(rawPrices.lastIndexOf(Math.max.apply(null, rawPrices))+1);
        buySell(rawPrices);
        if(leftStocks.length > 0){
            splitMaxPrice(leftStocks);
        }
        return;
    };

    splitMaxPrice(prices);

    return profitMade;

}

Answer 4

Otra forma de verlo:
En el preprocesamiento, para cada elemento a[i] encuentra a[j] st j > i y maximiza (a[j] - a[i])
entonces, lo mejor que puede hacer por un precio de a[i] es Comprar en a[i] y Vender en a[j] . Si no existe a[j] st a[j] > a[i] entonces a[i] no es un punto de Compra en absoluto.

Tiempo de preprocesamiento: O(N)

S[N-1] = A[N-1];
for(int i=N-2; i>=0; --i)
       S[i] = max(A[i], S[i+1]);

Aquí, S [i] es el precio al que debe vender un [i].

Resumiendo el beneficio total: O(N)

long long int Profit = 0;
    for(int i=0;i<N;++i)
          Profit += max(0,  (S[i]-A[i]) );

Answer 5

Otra solución de O (n) para esta tarea se puede hacer utilizando el mínimo local y el máximo para encontrar la mejor deferencia (ganancia) entre max y min sabiendo que max debe tener mayor índice que mínimo. También tenemos que mirar el mejor min local previo (implementación de C #).

public int[] GetBestShareBuyingStrategy(int[] price)
    {
        var n = price.Length;
        if (n <= 1)
            return null;

        var profit = 0;
        var min = 0;
        var max = 0;
        var lmin = 0;

        for (var i = 1; i < n; i++)
        {
            var lmax = i;
            var lp = price[lmax] - price[lmin];
            if (lp <= 0)
            {
                lmin = i;
            }
            else
            {
                var tp = price[lmax] - price[min];
                if (lp > tp && lp > profit)
                {
                    min = lmin;
                    max = lmax;
                    profit = lp;
                }
                else if (tp > profit)
                {
                    max = lmax;
                    profit = tp;
                }
            }
        }

        return profit > 0
            ? new [] {min, max}
            : null;
    }



    [Test]
    [TestCase(new[] { 10, 9, 8, 7, 3 })]
    [TestCase(new[] { 5, 5, 5, 5, 5 })]
    [TestCase(new[] { 5, 4, 4, 4 })]
    [TestCase(new[] { 5, 5, 3, 3 })]
    public void GetBestShareBuyingStrategy_When_no_sense_to_buy(int[] sharePrices)
    {
        var resultStrategy = GetBestShareBuyingStrategy(sharePrices);
        Assert.IsNull(resultStrategy);
    }

    [Test]
    [TestCase(new[] { 10, 8, 12, 20, 10 }, 1, 3)]
    [TestCase(new[] { 5, 8, 12, 20, 30 }, 0, 4)]
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)]
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)]
    [TestCase(new[] { 10, 2, 8, 1, 15, 20, 10, 22 }, 3, 7)]
    [TestCase(new[] { 1, 5, 2, 7, 3, 9, 8, 7 }, 0, 5)]
    [TestCase(new[] { 3, 5, 2, 7, 3, 9, 8, 7 }, 2, 5)]
    public void GetBestShareBuyingStrategy_PositiveStrategy(int[] sharePrices, int buyOn, int sellOn)
    {
        var resultStrategy = GetBestShareBuyingStrategy(sharePrices);
        Assert.AreEqual(buyOn, resultStrategy[0]);
        Assert.AreEqual(sellOn, resultStrategy[1]);
    }

Answer 6

aquí es algo más simple y fácil de entender;

    private static void BuyOnceAndSellONce()
    {
        int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 };
        int profit = 0;
        int minimumPrice = int.MaxValue;
        for (int i = 0; i < stock.Length; i++)
        {
            profit = Math.Max(profit, stock[i] - minimumPrice);
            minimumPrice = Math.Min(stock[i], minimumPrice);

        }
        Console.WriteLine("profit "  + profit);
    }

    private static void MultipleBuySellButNonOverlappingTransactions()
    {
        int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 };
        int totalProfit = 0;
        int currentProfit = 0;
        for (int i = 1; i < stock.Length;i++)
        {
            currentProfit = stock[i] - stock[i - 1];
            if (currentProfit > 0)
                totalProfit += currentProfit;
        }

        Console.WriteLine(totalProfit);
    }

Answer 7

tu lógica es correcta ...

vender en máximos globales ... pero no se requiere recurrencia ...

si el elemento es el máximo global ... ¡venda todas las acciones antes que yo!

Ahora el problema se reduce a la respuesta anterior + i + 1 a N ...

la recursividad no es necesaria ... ¡linealmente podemos calcular!

Answer 8

0.Inicie desde el final de la matriz para que no haya necesidad de recurse
1. smax = precio máximo de las acciones de la lista
2. Luego encuentra la ganancia asumiendo que has comprado todas las acciones hasta smax y la vendes al precio de smax

          public static void main(String[] args) {

          Scanner sc = new Scanner(System.in);
          int numOfTestCase = sc.nextInt();
          for (int i = 0; i < numOfTestCase; i++) {
                 int n = sc.nextInt();
                 long profit = 0;
                 int[] stockPrice = new int[n];

                 for (int j = 0; j < n; j++) {
                       stockPrice[j] = sc.nextInt();
                 }

                 int currMax = Integer.MIN_VALUE;

                 for (int j = n - 1; j >= 0; j--) {
                       if (currMax < stockPrice[j]) {
                              currMax = stockPrice[j];
                       }
                       profit += (currMax - stockPrice[j]);
                 }
                 System.out.println(profit);


          }
   }