Programa C++ para comprar acciones y vender para maximizar las ganancias

El costo de una acción en cada día se da en una array, encuentre la ganancia máxima que puede obtener comprando y vendiendo en esos días. Por ejemplo, si la array dada es {100, 180, 260, 310, 40, 535, 695}, la ganancia máxima se puede obtener comprando el día 0 y vendiendo el día 3. Nuevamente, compre el día 4 y venda el día 6. Si la array de precios dada se ordena en orden decreciente, entonces no se puede obtener ninguna ganancia.

Enfoque ingenuo: un enfoque simple es intentar comprar acciones y venderlas todos los días cuando sea rentable y seguir actualizando la ganancia máxima hasta el momento.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum profit
// that can be made after buying and
// selling the given stocks
int maxProfit(int price[],
              int start, int end)
{
    // If the stocks can't be bought
    if (end <= start)
        return 0;
 
    // Initialise the profit
    int profit = 0;
 
    // The day at which the stock
    // must be bought
    for (int i = start; i < end; i++)
    {
        // The day at which the
        // stock must be sold
        for (int j = i + 1; j <= end; j++)
        {
            // If buying the stock at ith day and
            // selling it at jth day is profitable
            if (price[j] > price[i])
            {
                // Update the current profit
                int curr_profit = price[j] - price[i] +
                                  maxProfit(price,
                                            start, i - 1) +
                                  maxProfit(price,
                                            j + 1, end);
 
                // Update the maximum profit so far
                profit = max(profit, curr_profit);
            }
        }
    }
    return profit;
}
 
// Driver code
int main()
{
    int price[] = {100, 180, 260, 310,
                    40, 535, 695};
    int n = sizeof(price) / sizeof(price[0]);
    cout << maxProfit(price, 0, n - 1);
    return 0;
}

Producción:

865

Complejidad de tiempo : O (n ^ 2) donde n es el tamaño de la array de stock dada

Enfoque eficiente: si se nos permite comprar y vender solo una vez, entonces podemos usar el siguiente algoritmo. Diferencia máxima entre dos elementos . Aquí se nos permite comprar y vender varias veces. 
El siguiente es el algoritmo para este problema.  

1. Encuentre los mínimos locales y guárdelos como índice inicial. Si no existe, regresa.
2. Encuentre los máximos locales. y guárdelo como un índice final. Si llegamos al final, establezca el final como el índice final.
3. Actualice la solución (Incremente el recuento de pares de compra-venta)
4. Repita los pasos anteriores si no se llega al final.

// C++ Program to find best buying
// and selling days
#include <bits/stdc++.h>
using namespace std;
 
// This function finds the buy sell
// schedule for maximum profit
void stockBuySell(int price[], int n)
{
    // Prices must be given for at
    // least two days
    if (n == 1)
        return;
 
    // Traverse through given price array
    int i = 0;
    while (i < n - 1)
    {
        // Find Local Minima
        // Note that the limit is (n-2) as we are
        // comparing present element to the next element
        while ((i < n - 1) &&
               (price[i + 1] <= price[i]))
            i++;
 
        // If we reached the end, break
        // as no further solution possible
        if (i == n - 1)
            break;
 
        // Store the index of minima
        int buy = i++;
 
        // Find Local Maxima
        // Note that the limit is (n-1) as we are
        // comparing to previous element
        while ((i < n) &&
               (price[i] >= price[i - 1]))
            i++;
 
        // Store the index of maxima
        int sell = i - 1;
 
        cout << "Buy on day: " << buy
             << "     Sell on day: " <<
                sell << endl;
    }
}
 
// Driver code
int main()
{
    // Stock prices on consecutive days
    int price[] = {100, 180, 260,
                   310, 40, 535, 695};
    int n = sizeof(price) / sizeof(price[0]);
 
    // Function call
    stockBuySell(price, n);
 
    return 0;
}
 
// This is code is contributed by rathbhupendra

Producción:

Buy on day: 0     Sell on day: 3
Buy on day: 4     Sell on day: 6

Complejidad del tiempo: el bucle externo se ejecuta hasta que me convierto en n-1. Los dos bucles internos incrementan el valor de I en cada iteración. Entonces la complejidad del tiempo total es O(n)

Espacio Auxiliar: O(1) 

Aproximación al Pico del Valle:

En este enfoque, solo necesitamos encontrar el siguiente elemento mayor y restarlo del elemento actual para que la diferencia siga aumentando hasta que alcancemos un mínimo. Si la secuencia es una secuencia decreciente, entonces la ganancia máxima posible es 0.

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Preprocessing helps the code
// run faster
#define fl(i, a, b)
for (int i = a; i < b; i++)
 
// Function that return
int maxProfit(int* prices, int size)
{
    // maxProfit adds up the difference
    // between adjacent elements if they
    // are in increasing order
    int maxProfit = 0;
 
    // The loop starts from 1 as its
    // comparing with the previous
    fl(i, 1, size) if (prices[i] > prices[i - 1]) maxProfit
        += prices[i] - prices[i - 1];
    return maxProfit;
}
 
// Driver code
int main()
{
    int prices[] = {100, 180, 260,
                    310, 40, 535, 695};
    int N = sizeof(prices) / sizeof(prices[0]);
    cout << maxProfit(prices, N) << endl;
    return 0;
}
// This code is contributed by Kingshuk Deb

Producción:

865

Complejidad temporal : O(n) Espacio
auxiliar : O(1)

¡ Consulte el artículo completo sobre Stock Buy Sell to Maximize Profit para obtener más detalles!