Maximice las ganancias negociando acciones en función de la tasa dada por día

Dada una array arr[] de N enteros positivos que denota el costo de vender y comprar una acción en cada uno de los N días. La tarea es encontrar la ganancia máxima que se puede obtener comprando una acción o vendiendo todas las acciones compradas previamente en un día en particular.
Ejemplos: 
 

Entrada: arr[] = {2, 3, 5} 
Salida: 5 
Explicación: 
Precio en el Día 1 = 2. Por lo tanto, compre las acciones en el Día 1 a este costo. Total_Spent = 2 
Precio en el Día 2 = 3. Por lo tanto, compre las acciones en el Día 2 a este costo. Total_Spent = 2 + 3 = 5 
Precio en el día 3 = 5. Si las acciones se venden a este precio, la ganancia será máxima. Por lo tanto, venda las acciones compradas el día 3 a este costo. Total_gained = 5*2 = 10 
Beneficio = 10 – 5 = 5
Entrada: arr[] = {8, 5, 1} 
Salida: 0 
Explicación: 
Después de comprar cualquier acción, no podemos vender ningún otro día porque conducirá a pérdida. Por lo tanto, el beneficio es 0. 
 

Enfoque: La idea es dividir los precios dados de las acciones en diferentes subarreglos de modo que cada subarreglo tenga el valor máximo al final del arreglo. Luego, encuentre la ganancia restando el valor de cada acción del último elemento en cada subarreglo. A continuación se muestran los pasos:
 

1. Recorra la array arr[] desde el final y considere arr[N – 1] como el precio actual más alto de una acción, digamos maxM .
2. Mientras el precio sea el más alto, todas las acciones compradas anteriormente obtendrán ganancias. Por lo tanto, muévase hacia la izquierda en arr[] y siga agregando maxM – arr[i] a la ganancia para todos los índices hasta que ocurra algún índice con un costo más alto que maxM .
3. Si se encuentra un precio más alto que maxM , entonces comprarlo causa una pérdida. Por lo tanto, establezca el costo de las existencias para ese día en particular, es decir, arr[i], como el valor actual de maxM y repita el paso 2 .
4. Después de atravesar la array, imprima la suma de la diferencia obtenida en el paso 2 para cada precio posible en arr[] .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum profit
int maxProfit(int* prices, int n)
{
    int profit = 0, currentDay = n - 1;
 
    // Start from the last day
    while (currentDay > 0) {
 
        int day = currentDay - 1;
 
        // Traverse and keep adding the
        // profit until a day with
        // price of stock higher
        // than currentDay is obtained
        while (day >= 0
            && (prices[currentDay]
                > prices[day])) {
 
            profit += (prices[currentDay]
                    - prices[day]);
 
            day--;
        }
 
        // Set this day as currentDay
        // with maximum cost of stock
        // currently
        currentDay = day;
    }
 
    // Return the profit
    return profit;
}
 
// Driver Code
int main()
{
    // Given array of prices
    int prices[] = { 2, 3, 5 };
 
    int N = sizeof(prices) / sizeof(prices[0]);
 
    // Function Call
    cout << maxProfit(prices, N);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to find the maximum profit
static int maxProfit(int[] prices, int n)
{
    int profit = 0, currentDay = n - 1;
 
    // Start from the last day
    while (currentDay > 0)
    {
        int day = currentDay - 1;
 
        // Traverse and keep adding the
        // profit until a day with
        // price of stock higher
        // than currentDay is obtained
        while (day >= 0 &&
            (prices[currentDay] > prices[day]))
        {
            profit += (prices[currentDay] -
                    prices[day]);
 
            day--;
        }
 
        // Set this day as currentDay
        // with maximum cost of stock
        // currently
        currentDay = day;
    }
 
    // Return the profit
    return profit;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array of prices
    int prices[] = { 2, 3, 5 };
 
    int N = prices.length;
 
    // Function Call
    System.out.print(maxProfit(prices, N));
}
}
 
// This code is contributed by Princi Singh

# Python3 program to implement
# above approach
 
# Function to find the maximum profit
def maxProfit(prices, n):
 
    profit = 0
    currentDay = n - 1
 
    # Start from the last day
    while (currentDay > 0):
        day = currentDay - 1
 
        # Traverse and keep adding the
        # profit until a day with
        # price of stock higher
        # than currentDay is obtained
        while (day >= 0 and
              (prices[currentDay] >
               prices[day])):
            profit += (prices[currentDay] -
                       prices[day])
                        
            day -= 1
         
        # Set this day as currentDay
        # with maximum cost of stock
        # currently
        currentDay = day;
     
    # Return the profit
    return profit;
 
# Driver Code
 
# Given array of prices
prices = [ 2, 3, 5 ]
 
N = len(prices)
 
# Function call
print(maxProfit(prices, N))
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the maximum profit
static int maxProfit(int[] prices, int n)
{
    int profit = 0, currentDay = n - 1;
 
    // Start from the last day
    while (currentDay > 0)
    {
        int day = currentDay - 1;
 
        // Traverse and keep adding the
        // profit until a day with
        // price of stock higher
        // than currentDay is obtained
        while (day >= 0 &&
              (prices[currentDay] > prices[day]))
        {
            profit += (prices[currentDay] -
                       prices[day]);
 
            day--;
        }
 
        // Set this day as currentDay
        // with maximum cost of stock
        // currently
        currentDay = day;
    }
 
    // Return the profit
    return profit;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array of prices
    int []prices = { 2, 3, 5 };
 
    int N = prices.Length;
 
    // Function call
    Console.Write(maxProfit(prices, N));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript program for the above problem.
 
// Function to find the maximum profit
function maxProfit(prices, n)
{
    let profit = 0, currentDay = n - 1;
   
    // Start from the last day
    while (currentDay > 0)
    {
        let day = currentDay - 1;
   
        // Traverse and keep adding the
        // profit until a day with
        // price of stock higher
        // than currentDay is obtained
        while (day >= 0 &&
              (prices[currentDay] > prices[day]))
        {
            profit += (prices[currentDay] -
                       prices[day]);
   
            day--;
        }
   
        // Set this day as currentDay
        // with maximum cost of stock
        // currently
        currentDay = day;
    }
   
    // Return the profit
    return profit;
}
     
// Driver code
 
    // Given array of prices
    let prices = [2, 3, 5];
   
    let N = prices.length;
   
    // Function call
    document.write(maxProfit(prices, N));
     
    // This code is contributed by susmitakundugoaldanga.
</script>

5

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