Dada una array de números enteros positivos que contienen el precio de las acciones y la tarifa de transacción, la tarea es encontrar la ganancia máxima y la diferencia de días en los que obtiene la ganancia máxima.
Ejemplos:
Input: arr[] = {6, 1, 7, 2, 8, 4}
transactionFee = 2
Output: 8 1
Input: arr[] = {7, 1, 5, 3, 6, 4}
transactionFee = 1
Output: 5 1
Explicación: Considerando el primer ejemplo: arr[] = {6, 1, 7, 2, 8, 4}, tarifa de transacción = 2
- Si compramos y vendemos el mismo día , no obtendremos ningún beneficio por lo que la diferencia entre la compra y la venta debe ser al menos 1.
- Con la diferencia de 1 día , si compramos una acción de 1 rupias y la vendemos 7 rupias con la diferencia del día 1, lo que significa comprar el día 2 y venderla al día siguiente , luego de pagar la tarifa de transacción de 2 rupias, es decir, 7- 1-2=4, obtendremos una ganancia de 4 rupias, lo mismo que si compramos el día 4 y lo vendemos el día 5 con la diferencia del día 1, obtendremos una ganancia de 4 rupias. Así que la ganancia total es de 8 rupias .
- Con la diferencia de 2 días , no obtendremos ningún beneficio .
- Con la diferencia de 3 días , si compramos acciones de 1 rupias y las vendemos 8 rupias con la diferencia de 3 días , lo que significa comprar el día 2 y venderlo después de 3 días , entonces la ganancia máxima después de pagar la tarifa de transacción de 2 rupias, es decir, 8- 1-2=5 obtendremos la ganancia de 5 rupias.
- Con la diferencia de 4 días , si compramos acciones de 1 rupias y las vendemos 4 rupias con la diferencia de 4 días , lo que significa comprar el día 2 y venderlo después de 4 días , luego de pagar la tarifa de transacción de 2 rupias, es decir, 4-1 -2=1, obtendremos una ganancia de 1 rupias .
- Con la diferencia de 5 días , no obtendremos ningún beneficio.
Acercarse:
- Recorre todo el arreglo con la diferencia de cada día.
- Verifique la ganancia restando el precio de cada día, incluida la tarifa de transacción.
- Rastree la ganancia máxima y almacene los diff_days en los que estamos obteniendo la ganancia máxima.
- Repita los pasos anteriores hasta que termine el bucle.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
int max_profit(int a[], int b[], int n, int fee)
{
int i, j, profit;
int l, r, diff_day = 1, sum = 0;
// b[0] will contain the maximum profit
b[0] = 0;
// b[1] will contain the day on which we are getting the
// maximum profit
b[1] = diff_day;
for (i = 1; i < n; i++) {
l = 0;
r = diff_day;
sum = 0;
for (j = n - 1; j >= i; j--) {
// here finding the max profit
profit = (a[r] - a[l]) - fee;
// if we get less then or equal to zero it means
// we are not getting the profit
if (profit > 0)
sum = sum + profit;
l++;
r++;
}
// check if sum is greater then maximum then store
// the new maximum
if (b[0] < sum) {
b[0] = sum;
b[1] = diff_day;
}
diff_day++;
}
return 0;
}
// Driver code
int main()
{
int arr[] = { 6, 1, 7, 2, 8, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int b[2];
int tranFee = 2;
max_profit(arr, b, n, tranFee);
cout << b[0] << ", " << b[1] << endl;
return 0;
}
C
// C implementation of above approach
#include <stdio.h>
int max_profit(int a[], int b[], int n, int fee)
{
int i, j, profit;
int l, r, diff_day = 1, sum = 0;
// b[0] will contain the maximum profit
b[0] = 0;
// b[1] will contain the day on which we are getting the
// maximum profit
b[1] = diff_day;
for (i = 1; i < n; i++) {
l = 0;
r = diff_day;
sum = 0;
for (j = n - 1; j >= i; j--) {
// here finding the max profit
profit = (a[r] - a[l]) - fee;
// if we get less then or equal to zero it means
// we are not getting the profit
if (profit > 0)
sum = sum + profit;
l++;
r++;
}
// check if sum is greater then maximum then store
// the new maximum
if (b[0] < sum) {
b[0] = sum;
b[1] = diff_day;
}
diff_day++;
}
return 0;
}
// Driver code
int main()
{
int arr[] = { 6, 1, 7, 2, 8, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int b[2];
int tranFee = 2;
max_profit(arr, b, n, tranFee);
printf("%d, %d", b[0], b[1]);
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java implementation of above approach
import java.util.*;
class solution
{
static int max_profit(int a[],int b[],int n,int fee)
{
int i, j, profit;
int l, r, diff_day = 1, sum = 0;
//b[0] will contain the maximum profit
b[0]=0;
//b[1] will contain the day
//on which we are getting the maximum profit
b[1]=diff_day;
for(i=1;i<n;i++)
{
l=0;
r=diff_day;
sum=0;
for(j=n-1;j>=i;j--)
{
//here finding the max profit
profit=(a[r]-a[l])-fee;
//if we get less then or equal to zero
// it means we are not getting the profit
if(profit>0)
{
sum=sum+profit;
}
l++;
r++;
}
//check if sum is greater then maximum then store the new maximum
if(b[0] < sum)
{
b[0] = sum;
b[1] = diff_day;
}
diff_day++;
}
return 0;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 6, 1, 7, 2, 8, 4 };
int n = arr.length;
int[] b = new int[2];
int tranFee = 2;
max_profit(arr, b, n, tranFee);
System.out.println(b[0]+", "+b[1]);
}
}
//This code is contributed by Surendra_Gangwar
Python3
# Python3 implementation of above approach def max_profit(a, b, n, fee): i, j, profit = 1, n - 1, 0 l, r, diff_day = 0, 0, 1 # b[0] will contain the maximum profit b[0] = 0 # b[1] will contain the day on which # we are getting the maximum profit b[1] = diff_day for i in range(1, n): l = 0 r = diff_day Sum = 0 for j in range(n - 1, i - 1, -1): # here finding the max profit profit = (a[r] - a[l]) - fee # if we get less then or equal to zero # it means we are not getting the profit if(profit > 0): Sum = Sum + profit l += 1 r += 1 # check if Sum is greater then maximum # then store the new maximum if(b[0] < Sum): b[0] = Sum b[1] = diff_day diff_day += 1 return 0 # Driver code arr = [6, 1, 7, 2, 8, 4] n = len(arr) b = [0 for i in range(2)] tranFee = 2 max_profit(arr, b, n, tranFee) print(b[0], ",", b[1]) # This code is contributed by # Mohit kumar 29
C#
// C# implementation of above approach
using System;
class GFG
{
static int max_profit(int []a, int []b,
int n, int fee)
{
int i, j, profit;
int l, r, diff_day = 1, sum = 0;
// b[0] will contain the
// maximum profit
b[0] = 0;
// b[1] will contain the day on which
// we are getting the maximum profit
b[1] = diff_day;
for(i = 1; i < n; i++)
{
l = 0; r = diff_day; sum = 0;
for(j = n - 1; j >= i; j--)
{
// here finding the max profit
profit = (a[r] - a[l]) - fee;
// if we get less then or equal
// to zero it means we are not
// getting the profit
if(profit > 0)
{
sum = sum + profit;
}
l++;
r++;
}
// check if sum is greater then maximum
// then store the new maximum
if(b[0] < sum)
{
b[0] = sum;
b[1] = diff_day;
}
diff_day++;
}
return 0;
}
// Driver code
static public void Main ()
{
int []arr = { 6, 1, 7, 2, 8, 4 };
int n = arr.Length;
int[] b = new int[2];
int tranFee = 2;
max_profit(arr, b, n, tranFee);
Console.WriteLine(b[0] + ", " + b[1]);
}
}
// This code is contributed by Sachin
PHP
<?php
// PHP implementation of above approach
function max_profit(&$a, &$b, $n, $fee)
{
$diff_day = 1;
$sum = 0;
// b[0] will contain the maximum profit
$b[0] = 0;
// b[1] will contain the day on which we
// are getting the maximum profit
$b[1] = $diff_day;
for($i = 1; $i < $n; $i++)
{
$l = 0;
$r = $diff_day;
$sum = 0;
for($j = $n - 1; $j >= $i; $j--)
{
// here finding the max profit
$profit = ($a[$r] - $a[$l]) - $fee;
// if we get less then or equal to zero
// it means we are not getting the profit
if($profit > 0)
{
$sum = $sum + $profit;
}
$l++;
$r++;
}
// check if sum is greater then maximum
// then store the new maximum
if($b[0] < $sum)
{
$b[0] = $sum;
$b[1] = $diff_day;
}
$diff_day++;
}
}
// Driver code
$arr = array(6, 1, 7, 2, 8, 4 );
$n = sizeof($arr);
$b = array();
$tranFee = 2;
max_profit($arr, $b, $n, $tranFee);
echo($b[0]);
echo(", ");
echo($b[1]);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript implementation of above approach
function max_profit(a , b , n , fee) {
var i, j, profit;
var l, r, diff_day = 1, sum = 0;
// b[0] will contain the maximum profit
b[0] = 0;
// b[1] will contain the day
// on which we are getting the maximum profit
b[1] = diff_day;
for (i = 1; i < n; i++) {
l = 0;
r = diff_day;
sum = 0;
for (j = n - 1; j >= i; j--) {
// here finding the max profit
profit = (a[r] - a[l]) - fee;
// if we get less then or equal to zero
// it means we are not getting the profit
if (profit > 0) {
sum = sum + profit;
}
l++;
r++;
}
// check if sum is greater then maximum
// then store the new maximum
if (b[0] < sum) {
b[0] = sum;
b[1] = diff_day;
}
diff_day++;
}
return 0;
}
// Driver code
var arr = [ 6, 1, 7, 2, 8, 4 ];
var n = arr.length;
var b = Array(2).fill(0);
var tranFee = 2;
max_profit(arr, b, n, tranFee);
document.write(b[0] + ", " + b[1]);
// This code contributed by Rajput-Ji
</script>
Producción
8, 1
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(1)
Mejor enfoque:
Igual que https://www.geeksforgeeks.org/stock-buy-sell/ pero también agrega días de diferencia
Python3
from typing import List, Tuple
def max_profit(prices: List[int], transaction_fee:int = 0) -> Tuple[int, int]:
n = len(prices)
start = 0
end = 1
profit = 0
max_profit_till_now = float('-inf')
diff = 0
while start < n - 1 and end < n:
while start < n - 1 and prices[start] > prices[start + 1]:
start += 1
end = start + 1
while end < n - 1 and prices[end] < prices[end + 1]:
end += 1
if end == n:
continue
cur_profit = prices[end] - prices[start] - transaction_fee
if cur_profit > 0:
profit += cur_profit
if max_profit_till_now < cur_profit:
max_profit_till_now = cur_profit
diff = end - start
start = end + 1
return profit, diff
print(max_profit([6, 1, 7, 2, 8, 4], 2))
Producción:
(8, 1)
Complejidad del tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por Mohd_Saliem y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA