Beneficio máximo comprando y vendiendo una acción como máximo K veces | Enfoque codicioso

En el comercio de acciones, un comprador compra acciones y las vende en una fecha futura. Dado el precio de las acciones de N días, el comerciante puede realizar como máximo K transacciones, donde una nueva transacción solo puede comenzar después de que se complete la transacción anterior. La tarea es averiguar el beneficio máximo que podría haber obtenido un comerciante de acciones. 

Ejemplos: 

Entrada: precios[] = {10, 22, 5, 75, 65, 80}, K = 2 
Salida: 87 
Explicación: El comerciante realiza 2 transacciones, la primera de las cuales es comprando al precio 10 y vendiendo al precio 22 seguido de una compra y venta a precio de 5 y 80 respectivamente. Por lo tanto, la ganancia obtenida es 87.

Entrada: precios[] = {12, 14, 17, 10, 14, 13, 12, 15}, K = 3 
Salida: 12 
Explicación: La primera transacción involucra la compra y venta a los precios 12 y 17 respectivamente. El segundo es una compra a un precio de 10 y una venta a 14, seguido de una compra a 12 y una venta a 15. Por lo tanto, la ganancia total obtenida es 12. 

Consulte este artículo para el enfoque de programación dinámica

Enfoque: este enfoque muestra cómo resolver este problema utilizando el enfoque codicioso :  

• Encuentre el precio más bajo de una acción antes de que suba, seguido del más alto antes de que los precios vuelvan a caer. Estos sirven como los precios actuales de compra y venta, respectivamente.
• Compare estos precios de compra y venta con los de la transacción anterior. Si el precio de compra actual es menor que el de la transacción anterior, elimine esa transacción y considere una nueva transacción con el precio de compra actual y el precio de venta de la transacción eliminada para aumentar la ganancia y continuar mientras la ganancia se pueda aumentar aún más con el precio de compra actual.
• Del mismo modo, compare los precios de venta y aumente la ganancia si es posible.
• Después de atravesar todos los precios N , agregue las ganancias K más altas. En caso de que el número de transacciones sea menor que K , calcule la suma de las ganancias de todas las transacciones.

El siguiente código es la implementación del enfoque anterior:  

// C++ program to find out maximum profit by
// buying and selling a share at most k times
// given the stock price of n days
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum profit
int maxProfit(int n, int k, int prices[])
{
    int ans = 0, buy = 0, sell = 0;
 
    stack<pair<int, int> > transaction;
    priority_queue<int> profits;
 
    while (sell < n) {
 
        buy = sell;
 
        // Find the farthest decreasing span
        // of prices before prices rise
        while (buy < n - 1
               && prices[buy] >= prices[buy + 1])
            buy++;
 
        sell = buy + 1;
 
        // Find the farthest increasing span
        // of prices before prices fall again
        while (sell < n
               && prices[sell] >= prices[sell - 1])
            sell++;
 
        // Check if the current buying price
        // is greater than that
        // of the previous transaction
        while (!transaction.empty()
               && prices[buy]
                      < prices[transaction.top().first]) {
            pair<int, int> p = transaction.top();
 
            // Store the profit
            profits.push(prices[p.second - 1]
                         - prices[p.first]);
 
            // Remove the previous transaction
            transaction.pop();
        }
 
        // Check if the current selling price is
        // less than that of the previous transactions
        while (!transaction.empty()
               && prices[sell - 1]
                      > prices[transaction.top().second - 1]) {
            pair<int, int> p = transaction.top();
 
            // Store the new profit
            profits.push(prices[p.second - 1]
                         - prices[buy]);
            buy = p.first;
 
            // Remove the previous transaction
            transaction.pop();
        }
 
        // Add the new transactions
        transaction.push({ buy, sell });
    }
 
    // Finally store the profits
    // of all the transactions
    while (!transaction.empty()) {
        profits.push(
            prices[transaction.top().second - 1]
            - prices[transaction.top().first]);
        transaction.pop();
    }
 
    // Add the highest K profits
    while (k && !profits.empty()) {
        ans += profits.top();
        profits.pop();
        --k;
    }
 
    // Return the maximum profit
    return ans;
}
 
// Driver code
int main()
{
    int k = 3;
    int prices[] = { 1, 12, 10, 7,
                     10, 13, 11, 10,
                     7, 6, 9 };
    int n = sizeof(prices) / sizeof(prices[0]);
 
    cout << "Maximum profit is "
         << maxProfit(n, k, prices);
 
    return 0;
}

// Java program to find out maximum profit
// by buying and selling a share at most k
// times given the stock price of n days
import java.util.*;
import java.lang.*;
 
class GFG{
 
// Function to return the maximum profit
static int maxProfit(int n, int k,
                     int prices[])
{
    int ans = 0, buy = 0, sell = 0;
     
    Stack<int[]> transaction = new Stack<>();
    PriorityQueue<Integer> profits = new PriorityQueue<>();
   
    while (sell < n)
    {
        buy = sell;
         
        // Find the farthest decreasing span
        // of prices before prices rise
        while (buy < n - 1 &&
        prices[buy] >= prices[buy + 1])
            buy++;
   
        sell = buy + 1;
   
        // Find the farthest increasing span
        // of prices before prices fall again
        while (sell < n &&
        prices[sell] >= prices[sell - 1])
            sell++;
   
        // Check if the current buying price
        // is greater than that of the
        // previous transaction
        while (!transaction.isEmpty() &&
               prices[buy] <
               prices[transaction.peek()[0]])
        {
            int[] p = transaction.peek();
             
            // Store the profit
            profits.add(prices[p[1] - 1] -
                        prices[p[0]]);
             
            // Remove the previous transaction
            transaction.pop();
        }
         
        // Check if the current selling price
        // is less than that of the previous
        // transactions
        while (!transaction.isEmpty() &&
               prices[sell - 1] >
               prices[transaction.peek()[1] - 1])
        {
            int[] p = transaction.peek();
             
            // Store the new profit
            profits.add(prices[p[1] - 1] -
                        prices[buy]);
                         
            buy = p[0];
             
            // Remove the previous transaction
            transaction.pop();
        }
         
        // Add the new transactions
        transaction.push(new int[]{ buy, sell });
    }
   
    // Finally store the profits
    // of all the transactions
    while (!transaction.isEmpty())
    {
        profits.add(
            prices[transaction.peek()[1] - 1] -
            prices[transaction.peek()[0]]);
             
        transaction.pop();
    }
   
    // Add the highest K profits
    while (k > 0 && !profits.isEmpty())
    {
        ans += profits.peek();
        profits.poll();
        --k;
    }
   
    // Return the maximum profit
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int k = 3;
    int prices[] = { 1, 12, 10, 7, 10, 13,
                     11, 10, 7, 6, 9 };
    int n = prices.length;
     
    System.out.println("Maximum profit is " +
                       maxProfit(n, k, prices));
}
}
 
// This code is contributed by offbeat

# Python3 program to find out maximum profit by
# buying and selling a share at most k times
# given the stock price of n days
 
# Function to return the maximum profit
def maxProfit(n, k, prices):
    ans = 0
    buy = 0
    sell = 0
    # stack
    transaction = []
    # priority queue
    profits = []
 
    while (sell < n):
        buy = sell
 
        # Find the farthest decreasing span
        # of prices before prices rise
        while (buy < n - 1 and prices[buy] >= prices[buy + 1]):
            buy += 1
 
        sell = buy + 1
 
        # Find the farthest increasing span
        # of prices before prices fall again
        while (sell < n and prices[sell] >= prices[sell - 1]):
            sell += 1
 
        # Check if the current buying price
        # is greater than that
        # of the previous transaction
        while (len(transaction) !=0 and prices[buy] < prices[transaction[len(transaction)-1][0]]):
            p = transaction[len(transaction)-1]
 
            # Store the profit
            profits.append(prices[p[1] - 1] - prices[p[0]])
 
            # Remove the previous transaction
            transaction.remove(transaction[len(transaction)-1])
 
        # Check if the current selling price is
        # less than that of the previous transactions
        profits.sort(reverse=True)
        while (len(transaction)!=0 and prices[sell - 1] > prices[transaction[len(transaction)-1][1] - 1]):
            p = transaction[len(transaction)-1]
 
            # Store the new profit
            profits.append(prices[p[1] - 1] - prices[buy])
            buy = p[0]
 
            # Remove the previous transaction
            transaction.remove(transaction[len(transaction)-1])
 
        # Add the new transactions
        transaction.append([buy, sell])
     
    profits.sort(reverse=True)
    # Finally store the profits
    # of all the transactions
    while (len(transaction) != 0):
        profits.append(prices[transaction[len(transaction)-1][1]- 1]-prices[transaction[len(transaction)-1][0]])
        transaction.remove(transaction[len(transaction)-1])
 
    profits.sort(reverse=True)
    # Add the highest K profits
    while (k!=0 and len(profits)!=0):
        ans += profits[0]
        profits.remove(profits[0])
        k -= 1
 
    # Return the maximum profit
    return ans
 
# Driver code
if __name__ == '__main__':
    k = 3
    prices = [1, 12, 10, 7,10, 13, 11, 10,7, 6, 9]
    n = len(prices)
 
    print("Maximum profit is",maxProfit(n, k, prices))
 
# This code is contributed by Surendra_Gangwar

<script>
 
// JavaScript program to find out maximum profit by
// buying && selling a share at most k times
// given the stock price of n days
 
// Function to return the maximum profit
function maxProfit(n, k, prices){
    let ans = 0
    let buy = 0
    let sell = 0
    // stack
    let transaction = []
    // priority queue
    let profits = []
 
    while (sell < n){
        buy = sell
 
        // Find the farthest decreasing span
        // of prices before prices rise
        while (buy < n - 1 && prices[buy] >= prices[buy + 1])
            buy += 1
 
        sell = buy + 1
 
        // Find the farthest increasing span
        // of prices before prices fall again
        while (sell < n && prices[sell] >= prices[sell - 1])
            sell += 1
 
        // Check if the current buying price
        // is greater than that
        // of the previous transaction
        while (transaction.length !=0 && prices[buy] < prices[transaction[transaction.length-1][0]]){
            p = transaction[transaction.length-1]
 
            // Store the profit
            profits.push(prices[p[1] - 1] - prices[p[0]])
 
            // Remove the previous transaction
            transaction.pop()
      }
 
        // Check if the current selling price is
        // less than that of the previous transactions
        profits.sort((a,b)=>b-a)
        while (transaction.length!=0 && prices[sell - 1] > prices[transaction[transaction.length-1][1] - 1]){
            let p = transaction[transaction.length-1]
 
            // Store the new profit
            profits.push(prices[p[1] - 1] - prices[buy])
            buy = p[0]
 
            // Remove the previous transaction
            transaction.pop()
      }
 
        // Add the new transactions
        transaction.push([buy, sell])
   }
     
    profits.sort((a,b)=>b-a)
    // Finally store the profits
    // of all the transactions
    while (transaction.length != 0){
        profits.push(prices[transaction[transaction.length-1][1]- 1]-prices[transaction[transaction.length-1][0]])
        transaction.pop()
   }
    profits.sort((a,b)=>b-a)
    // Add the highest K profits
    while (k!=0 && profits.length!=0){
        ans += profits[0]
        profits.shift()
        k -= 1
   }
 
    // Return the maximum profit
    return ans
}
 
// Driver code
let k = 3
let prices = [1, 12, 10, 7,10, 13, 11, 10,7, 6, 9]
let n = prices.length
 
document.write("Maximum profit is",maxProfit(n, k, prices),"</br>")
 
// This code is contributed by Shinjanpatra
 
</script>

Maximum profit is 20

Complejidad de tiempo: O(N * log N)

Espacio Auxiliar: O(N)