En el comercio diario de acciones, un comprador compra acciones por la mañana y las vende el mismo día. Si el comerciante puede realizar como máximo 2 transacciones en un día, mientras que la segunda transacción solo puede comenzar después de que se complete la primera (Comprar-> vender-> Comprar-> vender). Dados los precios de las acciones a lo largo del día, averigüe la ganancia máxima que podría haber obtenido un operador de acciones.
Ejemplos:
Input: price[] = {10, 22, 5, 75, 65, 80}
Output: 87
Trader earns 87 as sum of 12, 75
Buy at 10, sell at 22,
Buy at 5 and sell at 80
Input: price[] = {2, 30, 15, 10, 8, 25, 80}
Output: 100
Trader earns 100 as sum of 28 and 72
Buy at price 2, sell at 30, buy at 8 and sell at 80
Input: price[] = {100, 30, 15, 10, 8, 25, 80};
Output: 72
Buy at price 8 and sell at 80.
Input: price[] = {90, 80, 70, 60, 50}
Output: 0
Not possible to earn.
Una solución simple es considerar cada índice ‘i’ y hacer lo siguiente
Beneficio máximo con dos transacciones como máximo =
MAX {beneficio máximo con una transacción y precio de subarreglo[0..i] +
beneficio máximo con una transacción y precio de subarreglo[i+1..n-1]}
i varía de 0 a n -1.
El máximo posible usando una transacción se puede calcular usando el siguiente algoritmo O(n)
La diferencia máxima entre dos elementos tal que el elemento más grande aparece después del número más pequeño
La complejidad de tiempo de la solución simple anterior es O(n 2 ).
Podemos hacer esto O(n) usando la siguiente Solución Eficiente . La idea es almacenar el máximo beneficio posible de cada subarreglo y resolver el problema en las siguientes dos fases.
1) Cree una tabla de ganancias[0..n-1] e inicialice todos los valores en ella 0.
2) Recorra el precio[] de derecha a izquierda y actualice las ganancias[i] de modo que las ganancias[i] almacenen las ganancias máximas que se pueden obtener de una transacción en el subarreglo precio[i..n-1]
3) Recorra el precio[] de izquierda a derecha y actualice el beneficio[i] de modo que el beneficio[i] almacene el beneficio máximo de modo que el beneficio[i] contenga el beneficio máximo alcanzable de dos transacciones en precio de subarreglo[0..i].
4) Devolución de beneficios[n-1]
Para realizar el paso 2, debemos realizar un seguimiento del precio máximo de derecha a izquierda, y para realizar el paso 3, debemos realizar un seguimiento del precio mínimo de izquierda a derecha. ¿Por qué viajamos en sentido inverso? La idea es ahorrar espacio, en el tercer paso usamos el mismo arreglo para ambos propósitos, máximo con 1 transacción y máximo con 2 transacciones. Después de la iteración i, la array profit[0..i] contiene la ganancia máxima con 2 transacciones, y profit[i+1..n-1] contiene la ganancia con dos transacciones.
A continuación se muestran las implementaciones de la idea anterior.
C++
// C++ program to find maximum
// possible profit with at most
// two transactions
#include <bits/stdc++.h>
using namespace std;
// Returns maximum profit with
// two transactions on a given
// list of stock prices, price[0..n-1]
int maxProfit(int price[], int n)
{
// Create profit array and
// initialize it as 0
int* profit = new int[n];
for (int i = 0; i < n; i++)
profit[i] = 0;
/* Get the maximum profit with
only one transaction
allowed. After this loop,
profit[i] contains maximum
profit from price[i..n-1]
using at most one trans. */
int max_price = price[n - 1];
for (int i = n - 2; i >= 0; i--) {
// max_price has maximum
// of price[i..n-1]
if (price[i] > max_price)
max_price = price[i];
// we can get profit[i] by taking maximum of:
// a) previous maximum, i.e., profit[i+1]
// b) profit by buying at price[i] and selling at
// max_price
profit[i]
= max(profit[i + 1], max_price - price[i]);
}
/* Get the maximum profit with two transactions allowed
After this loop, profit[n-1] contains the result */
int min_price = price[0];
for (int i = 1; i < n; i++) {
// min_price is minimum price in price[0..i]
if (price[i] < min_price)
min_price = price[i];
// Maximum profit is maximum of:
// a) previous maximum, i.e., profit[i-1]
// b) (Buy, Sell) at (min_price, price[i]) and add
// profit of other trans. stored in profit[i]
profit[i] = max(profit[i - 1],
profit[i] + (price[i] - min_price));
}
int result = profit[n - 1];
delete[] profit; // To avoid memory leak
return result;
}
// Driver code
int main()
{
int price[] = { 2, 30, 15, 10, 8, 25, 80 };
int n = sizeof(price) / sizeof(price[0]);
cout << "Maximum Profit = " << maxProfit(price, n);
return 0;
}
Java
class Profit {
// Returns maximum profit
// with two transactions on a
// given list of stock prices,
// price[0..n-1]
static int maxProfit(int price[], int n)
{
// Create profit array
// and initialize it as 0
int profit[] = new int[n];
for (int i = 0; i < n; i++)
profit[i] = 0;
/* Get the maximum profit
with only one transaction
allowed. After this loop,
profit[i] contains
maximum profit from
price[i..n-1] using at most
one trans. */
int max_price = price[n - 1];
for (int i = n - 2; i >= 0; i--) {
// max_price has maximum
// of price[i..n-1]
if (price[i] > max_price)
max_price = price[i];
// we can get profit[i]
// by taking maximum of:
// a) previous maximum,
// i.e., profit[i+1]
// b) profit by buying
// at price[i] and selling
// at
// max_price
profit[i] = Math.max(profit[i + 1],
max_price - price[i]);
}
/* Get the maximum profit
with two transactions allowed
After this loop, profit[n-1]
contains the result
*/
int min_price = price[0];
for (int i = 1; i < n; i++) {
// min_price is minimum
// price in price[0..i]
if (price[i] < min_price)
min_price = price[i];
// Maximum profit is maximum of:
// a) previous maximum, i.e., profit[i-1]
// b) (Buy, Sell) at (min_price, price[i]) and
// add
// profit of other trans.
// stored in profit[i]
profit[i] = Math.max(
profit[i - 1],
profit[i] + (price[i] - min_price));
}
int result = profit[n - 1];
return result;
}
// Driver Code
public static void main(String args[])
{
int price[] = { 2, 30, 15, 10, 8, 25, 80 };
int n = price.length;
System.out.println("Maximum Profit = "
+ maxProfit(price, n));
}
} /* This code is contributed by Rajat Mishra */
Python3
# Returns maximum profit with
# two transactions on a given
# list of stock prices price[0..n-1]
def maxProfit(price, n):
# Create profit array and initialize it as 0
profit = [0]*n
# Get the maximum profit
# with only one transaction
# allowed. After this loop,
# profit[i] contains maximum
# profit from price[i..n-1]
# using at most one trans.
max_price = price[n-1]
for i in range(n-2, 0, -1):
if price[i] > max_price:
max_price = price[i]
# we can get profit[i] by
# taking maximum of:
# a) previous maximum,
# i.e., profit[i+1]
# b) profit by buying at
# price[i] and selling at
# max_price
profit[i] = max(profit[i+1], max_price - price[i])
# Get the maximum profit
# with two transactions allowed
# After this loop, profit[n-1]
# contains the result
min_price = price[0]
for i in range(1, n):
if price[i] < min_price:
min_price = price[i]
# Maximum profit is maximum of:
# a) previous maximum,
# i.e., profit[i-1]
# b) (Buy, Sell) at
# (min_price, A[i]) and add
# profit of other trans.
# stored in profit[i]
profit[i] = max(profit[i-1], profit[i]+(price[i]-min_price))
result = profit[n-1]
return result
# Driver function
price = [2, 30, 15, 10, 8, 25, 80]
print ("Maximum profit is", maxProfit(price, len(price)))
# This code is contributed by __Devesh Agrawal__
C#
// C# program to find maximum possible profit
// with at most two transactions
using System;
class GFG {
// Returns maximum profit with two
// transactions on a given list of
// stock prices, price[0..n-1]
static int maxProfit(int[] price, int n)
{
// Create profit array and initialize
// it as 0
int[] profit = new int[n];
for (int i = 0; i < n; i++)
profit[i] = 0;
/* Get the maximum profit with only
one transaction allowed. After this
loop, profit[i] contains maximum
profit from price[i..n-1] using at
most one trans. */
int max_price = price[n - 1];
for (int i = n - 2; i >= 0; i--) {
// max_price has maximum of
// price[i..n-1]
if (price[i] > max_price)
max_price = price[i];
// we can get profit[i] by taking
// maximum of:
// a) previous maximum, i.e.,
// profit[i+1]
// b) profit by buying at price[i]
// and selling at max_price
profit[i] = Math.Max(profit[i + 1],
max_price - price[i]);
}
/* Get the maximum profit with two
transactions allowed After this loop,
profit[n-1] contains the result */
int min_price = price[0];
for (int i = 1; i < n; i++) {
// min_price is minimum price in
// price[0..i]
if (price[i] < min_price)
min_price = price[i];
// Maximum profit is maximum of:
// a) previous maximum, i.e.,
// profit[i-1]
// b) (Buy, Sell) at (min_price,
// price[i]) and add profit of
// other trans. stored in
// profit[i]
profit[i] = Math.Max(
profit[i - 1],
profit[i] + (price[i] - min_price));
}
int result = profit[n - 1];
return result;
}
// Driver code
public static void Main()
{
int[] price = { 2, 30, 15, 10, 8, 25, 80 };
int n = price.Length;
Console.Write("Maximum Profit = "
+ maxProfit(price, n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find maximum
// possible profit with at most
// two transactions
// Returns maximum profit with
// two transactions on a given
// list of stock prices, price[0..n-1]
function maxProfit($price, $n)
{
// Create profit array and
// initialize it as 0
$profit = array();
for ($i = 0; $i < $n; $i++)
$profit[$i] = 0;
// Get the maximum profit with
// only one transaction allowed.
// After this loop, profit[i]
// contains maximum profit from
// price[i..n-1] using at most
// one trans.
$max_price = $price[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
{
// max_price has maximum
// of price[i..n-1]
if ($price[$i] > $max_price)
$max_price = $price[$i];
// we can get profit[i] by
// taking maximum of:
// a) previous maximum,
// i.e., profit[i+1]
// b) profit by buying at
// price[i] and selling at
// max_price
if($profit[$i + 1] >
$max_price-$price[$i])
$profit[$i] = $profit[$i + 1];
else
$profit[$i] = $max_price -
$price[$i];
}
// Get the maximum profit with
// two transactions allowed.
// After this loop, profit[n-1]
// contains the result
$min_price = $price[0];
for ($i = 1; $i < $n; $i++)
{
// min_price is minimum
// price in price[0..i]
if ($price[$i] < $min_price)
$min_price = $price[$i];
// Maximum profit is maximum of:
// a) previous maximum,
// i.e., profit[i-1]
// b) (Buy, Sell) at (min_price,
// price[i]) and add
// profit of other trans.
// stored in profit[i]
$profit[$i] = max($profit[$i - 1],
$profit[$i] +
($price[$i] - $min_price));
}
$result = $profit[$n - 1];
return $result;
}
// Driver Code
$price = array(2, 30, 15, 10,
8, 25, 80);
$n = sizeof($price);
echo "Maximum Profit = ".
maxProfit($price, $n);
// This code is contributed
// by Arnab Kundu
?>
Javascript
<script>
// JavaScript program to find maximum
// possible profit with at most
// two transactions
// Returns maximum profit with
// two transactions on a given
// list of stock prices, price[0..n-1]
function maxProfit(price, n)
{
// Create profit array and
// initialize it as 0
let profit = new Array(n);
for(let i = 0; i < n; i++)
profit[i] = 0;
/* Get the maximum profit with
only one transaction
allowed. After this loop,
profit[i] contains maximum
profit from price[i..n-1]
using at most one trans. */
let max_price = price[n - 1];
for(let i = n - 2; i >= 0; i--)
{
// max_price has maximum
// of price[i..n-1]
if (price[i] > max_price)
max_price = price[i];
// We can get profit[i] by taking maximum of:
// a) previous maximum, i.e., profit[i+1]
// b) profit by buying at price[i] and selling at
// max_price
profit[i] = Math.max(profit[i + 1],
max_price - price[i]);
}
// Get the maximum profit with
// two transactions allowed
// After this loop, profit[n-1]
// contains the result
let min_price = price[0];
for(let i = 1; i < n; i++)
{
// min_price is minimum price
// in price[0..i]
if (price[i] < min_price)
min_price = price[i];
// Maximum profit is maximum of:
// a) previous maximum, i.e., profit[i-1]
// b) (Buy, Sell) at (min_price, price[i]) and add
// profit of other trans. stored in profit[i]
profit[i] = Math.max(profit[i - 1],
profit[i] + (price[i] - min_price));
}
let result = profit[n - 1];
return result;
}
// Driver code
let price = [ 2, 30, 15, 10, 8, 25, 80 ];
let n = price.length;
document.write("Maximum Profit = " +
maxProfit(price, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción
Maximum Profit = 100
La complejidad temporal de la solución anterior es O(n).
Paradigma Algorítmico: Programación Dinámica
Otro enfoque:
Inicialice cuatro variables para ocuparse de la primera compra, la primera venta, la segunda compra, la segunda venta. Establezca la primera compra y la segunda compra como INT_MIN y la primera y segunda venta como 0. Esto es para asegurarse de obtener ganancias de las transacciones. Itere a través de la array y devuelva la segunda venta, ya que almacenará la máxima ganancia.
C++
#include <iostream>
#include<climits>
using namespace std;
int maxtwobuysell(int arr[],int size) {
int first_buy = INT_MIN;
int first_sell = 0;
int second_buy = INT_MIN;
int second_sell = 0;
for(int i=0;i<size;i++) {
first_buy = max(first_buy,-arr[i]);//we set prices to negative, so the calculation of profit will be convenient
first_sell = max(first_sell,first_buy+arr[i]);
second_buy = max(second_buy,first_sell-arr[i]);//we can buy the second only after first is sold
second_sell = max(second_sell,second_buy+arr[i]);
}
return second_sell;
}
int main() {
int arr[] = {2, 30, 15, 10, 8, 25, 80};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<maxtwobuysell(arr,size);
return 0;
}
Java
import java.util.*;
class GFG{
static int maxtwobuysell(int arr[],int size) {
int first_buy = Integer.MIN_VALUE;
int first_sell = 0;
int second_buy = Integer.MIN_VALUE;
int second_sell = 0;
for(int i = 0; i < size; i++) {
first_buy = Math.max(first_buy,-arr[i]);
first_sell = Math.max(first_sell,first_buy+arr[i]);
second_buy = Math.max(second_buy,first_sell-arr[i]);
second_sell = Math.max(second_sell,second_buy+arr[i]);
}
return second_sell;
}
public static void main(String[] args)
{
int arr[] = {2, 30, 15, 10, 8, 25, 80};
int size = arr.length;
System.out.print(maxtwobuysell(arr,size));
}
}
// This code is contributed by gauravrajput1
Python3
import sys def maxtwobuysell(arr, size): first_buy = -sys.maxsize; first_sell = 0; second_buy = -sys.maxsize; second_sell = 0; for i in range(size): first_buy = max(first_buy, -arr[i]); first_sell = max(first_sell, first_buy + arr[i]); second_buy = max(second_buy, first_sell - arr[i]); second_sell = max(second_sell, second_buy + arr[i]); return second_sell; if __name__ == '__main__': arr = [ 2, 30, 15, 10, 8, 25, 80 ]; size = len(arr); print(maxtwobuysell(arr, size)); # This code is contributed by gauravrajput1
C#
using System;
public class GFG{
static int maxtwobuysell(int []arr,int size) {
int first_buy = int.MinValue;
int first_sell = 0;
int second_buy = int.MinValue;
int second_sell = 0;
for(int i = 0; i < size; i++) {
first_buy = Math.Max(first_buy,-arr[i]);
first_sell = Math.Max(first_sell,first_buy+arr[i]);
second_buy = Math.Max(second_buy,first_sell-arr[i]);
second_sell = Math.Max(second_sell,second_buy+arr[i]);
}
return second_sell;
}
public static void Main(String[] args)
{
int []arr = {2, 30, 15, 10, 8, 25, 80};
int size = arr.Length;
Console.Write(maxtwobuysell(arr,size));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
function maxtwobuysell(arr , size) {
var first_buy = -1000;
var first_sell = 0;
var second_buy = -1000;
var second_sell = 0;
for (var i = 0; i < size; i++) {
first_buy = Math.max(first_buy, -arr[i]);
first_sell = Math.max(first_sell, first_buy + arr[i]);
second_buy = Math.max(second_buy, first_sell - arr[i]);
second_sell = Math.max(second_sell, second_buy + arr[i]);
}
return second_sell;
}
var arr = [ 2, 30, 15, 10, 8, 25, 80 ];
var size = arr.length;
document.write(maxtwobuysell(arr, size));
// This code is contributed by gauravrajput1
</script>
Producción
100
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA