Programa Python para la compra de acciones y la venta 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:

# Python3 implementation of the approach
 
# Function to return the maximum profit
# that can be made after buying and
# selling the given stocks
def maxProfit(price, start, end):
 
    # If the stocks can't be bought
    if (end <= start):
        return 0;
 
    # Initialise the profit
    profit = 0;
 
    # The day at which the stock
    # must be bought
    for i in range(start, end, 1):
 
        # The day at which the
        # stock must be sold
        for j in range(i+1, end+1):
 
            # If buying the stock at ith day and
            # selling it at jth day is profitable
            if (price[j] > price[i]):
                 
                # Update the current profit
                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
if __name__ == '__main__':
    price = [100, 180, 260,
             310, 40, 535, 695];
    n = len(price);
    print(maxProfit(price, 0, n - 1));
# This code is contributed by Rajput-Ji

Producción:

865

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.

# Python3 Program to find
# best buying and selling days
 
# This function finds the buy sell
# schedule for maximum profit
def stockBuySell(price, n):
     
    # Prices must be given for at
    # least two days
    if (n == 1):
        return
     
    # Traverse through given price array
    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)) and
                (price[i + 1] <= price[i])):
            i += 1
         
        # If we reached the end, break
        # as no further solution possible
        if (i == n - 1):
            break
         
        # Store the index of minima
        buy = i
        i += 1
         
        # Find Local Maxima
        # Note that the limit is (n-1) as we are
        # comparing to previous element
        while ((i < n) and
               (price[i] >= price[i - 1])):
            i += 1
             
        # Store the index of maxima
        sell = i - 1
         
        print("Buy on day: ",buy,"    ",
                "Sell on day: ",sell)
         
# Driver code
 
# Stock prices on consecutive days
price = [100, 180, 260,
         310, 40, 535, 695]
n = len(price)
 
# Function call
stockBuySell(price, n)
# This is code contributed by SHUBHAMSINGH10

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)

Complejidad espacial : O (1) ya que usa variables constantes

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.

# Python3 program for the
# above approach
def max_profit(prices: list,
               days: int) -> int:
    profit = 0
 
    for i in range(1, days):
 
        # Checks if elements are adjacent
        # and in increasing order
        if prices[i] > prices[i-1]:
 
            # Difference added to 'profit'
            profit += prices[i] - prices[i-1]
 
    return profit
 
# Driver Code
if __name__ == '__main__':
 
    # Stock prices on consecutive days
    prices = [100, 180, 260,
              310, 40, 535, 695]
 
    # Function call
    profit = max_profit(prices, len(prices))
    print(profit)
 
 # This code is contributed by vishvofficial.

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!