Programa Java 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:

// Java implementation of the approach
import java.util.*;
class GFG{
 
// Function to return the maximum profit
// that can be made after buying and
// selling the given stocks
static 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 = Math.max(profit,
                                  curr_profit);
            }
        }
    }
    return profit;
}
 
// Driver code
public static void main(String[] args)
{
    int price[] = {100, 180, 260, 310,
                   40, 535, 695};
    int n = price.length;
    System.out.print(maxProfit(
                     price, 0, n - 1));
}
}
// This code is contributed by PrinciRaj1992

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.

// Program to find best buying and
// selling days
import java.util.ArrayList;
 
// Solution structure
class Interval
{
    int buy, sell;
}
 
class StockBuySell
{
    // 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;
 
        int count = 0;
 
        // Solution array
        ArrayList<Interval> sol =
                  new ArrayList<Interval>();
 
        // 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;
 
            Interval e = new Interval();
            e.buy = i++;
            // Store the index of minima
 
            // 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
            e.sell = i - 1;
            sol.add(e);
 
            // Increment number of buy/sell
            count++;
        }
 
        // print solution
        if (count == 0)
            System.out.println(
            "There is no day when buying the stock " +
            "will make profit");
        else
            for (int j = 0; j < count; j++)
                System.out.println(
                "Buy on day: " + sol.get(j).buy +
                "        " + "Sell on day : " +
                sol.get(j).sell);
 
        return;
    }
 
    // Driver code
    public static void main(String args[])
    {
        StockBuySell stock = new StockBuySell();
 
        // stock prices on consecutive days
        int price[] = {100, 180, 260,
                       310, 40, 535, 695};
        int n = price.length;
 
        // function call
        stock.stockBuySell(price, n);
    }
}
// This code is contributed by Mayank Jaiswal

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) 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.

// Java program for the above approach
import java.io.*;
class GFG
{
    static 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
        for (int i = 1; i < size; i++)
            if (prices[i] > prices[i - 1])
                maxProfit += prices[i] - prices[i - 1];
        return maxProfit;
    }
 
    // Driver code
    public static void main(String[] args)
    {   
        // stock prices on consecutive days
        int price[] = {100, 180, 260,
                       310, 40, 535, 695};
        int n = price.length;
 
        // function call
        System.out.println(maxProfit(price, n));
    }
}
// This code is contributed by rajsanghavi9.

Producción:

865

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

Este artículo fue compilado por Ashish Anand y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.