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. De nuevo, compre el día 4 y venda el día 6. Si el conjunto de precios dado 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.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum profit
// that can be made after buying and
// selling the given stocks
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 = max(profit, curr_profit);
}
}
}
return profit;
}
// Driver code
int main()
{
int price[] = { 100, 180, 260, 310,
40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);
cout << maxProfit(price, 0, n - 1);
return 0;
}
C
// Importing the required header files
#include <stdio.h>
// Creating MACRO for finding the maximum number
#define max(x, y)(((x) > (y)) ? (x) : (y))
// Creating MACRO for finding the minimum number
#define min(x, y)(((x) < (y)) ? (x) : (y))
// Function to return the maximum profit
// that can be made after buying and
// selling the given stocks
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 = max(profit, curr_profit);
}
}
}
return profit;
}
// Driver Code
int main()
{
int price[] = { 100, 180, 260, 310,
40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);
printf("%d", maxProfit(price, 0, n - 1));
return 0;
}
Java
// 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
Python3
# Python3 implementation of the approach # Function to return the maximum profit # that can be made after buying and # selling the given stocks def maxProfit(price, start, end): # If the stocks can't be bought if (end <= start): return 0; # Initialise the profit profit = 0; # The day at which the stock # must be bought for i in range(start, end, 1): # The day at which the # stock must be sold for j in range(i+1, end+1): # If buying the stock at ith day and # selling it at jth day is profitable if (price[j] > price[i]): # Update the current profit curr_profit = price[j] - price[i] +\ maxProfit(price, start, i - 1)+ \ maxProfit(price, j + 1, end); # Update the maximum profit so far profit = max(profit, curr_profit); return profit; # Driver code if __name__ == '__main__': price = [100, 180, 260, 310, 40, 535, 695]; n = len(price); print(maxProfit(price, 0, n - 1)); # This code is contributed by Rajput-Ji
C#
// C# implementation of the approach
using System;
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;
Console.Write(maxProfit(price, 0, n - 1));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function to return the maximum profit
// that can be made after buying and
// selling the given stocks
function maxProfit( price, start, end)
{
// If the stocks can't be bought
if (end <= start)
return 0;
// Initialise the profit
let profit = 0;
// The day at which the stock
// must be bought
for (let i = start; i < end; i++) {
// The day at which the
// stock must be sold
for (let 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
let 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 program
let price = [ 100, 180, 260, 310,
40, 535, 695 ];
let n = price.length;
document.write(maxProfit(price, 0, n - 1));
</script>
C++
// C++ Program to find best buying and selling days
#include <bits/stdc++.h>
using namespace std;
// 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;
// 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;
// Store the index of minima
int buy = i++;
// 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
int sell = i - 1;
cout << "Buy on day: " << buy
<< "\t Sell on day: " << sell << endl;
}
}
// Driver code
int main()
{
// Stock prices on consecutive days
int price[] = { 100, 180, 260, 310, 40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);
// Function call
stockBuySell(price, n);
return 0;
}
// This is code is contributed by rathbhupendra
C
// Program to find best buying and selling days
#include <stdio.h>
// solution structure
struct Interval {
int buy;
int sell;
};
// 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; // count of solution pairs
// solution vector
Interval sol[n / 2 + 1];
// 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;
// Store the index of minima
sol[count].buy = i++;
// 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
sol[count].sell = i - 1;
// Increment count of buy/sell pairs
count++;
}
// print solution
if (count == 0)
printf("There is no day when buying the stock will make profitn");
else {
for (int i = 0; i < count; i++)
printf("Buy on day: %dt Sell on day: %dn", sol[i].buy, sol[i].sell);
}
return;
}
// Driver program to test above functions
int main()
{
// stock prices on consecutive days
int price[] = { 100, 180, 260, 310, 40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);
// function call
stockBuySell(price, n);
return 0;
}
Java
// 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;
}
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 has been contributed by Mayank Jaiswal
Python3
# Python3 Program to find
# best buying and selling days
# This function finds the buy sell
# schedule for maximum profit
def stockBuySell(price, n):
# Prices must be given for at least two days
if (n == 1):
return
# Traverse through given price array
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)) and
(price[i + 1] <= price[i])):
i += 1
# If we reached the end, break
# as no further solution possible
if (i == n - 1):
break
# Store the index of minima
buy = i
i += 1
# Find Local Maxima
# Note that the limit is (n-1) as we are
# comparing to previous element
while ((i < n) and (price[i] >= price[i - 1])):
i += 1
# Store the index of maxima
sell = i - 1
print("Buy on day: ",buy,"\t",
"Sell on day: ",sell)
# Driver code
# Stock prices on consecutive days
price = [100, 180, 260, 310, 40, 535, 695]
n = len(price)
# Function call
stockBuySell(price, n)
# This is code contributed by SHUBHAMSINGH10
C#
// C# program to find best buying and selling days
using System;
using System.Collections.Generic;
// Solution structure
class Interval
{
public int buy, sell;
}
public 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
List<Interval> sol = new List<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)
Console.WriteLine("There is no day when buying the stock "
+ "will make profit");
else
for (int j = 0; j < count; j++)
Console.WriteLine("Buy on day: " + sol[j].buy
+ " "
+ "Sell on day : " + sol[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 PrinciRaj1992
Javascript
<script>
// JavaScript program for the above approach
// This function finds the buy sell
// schedule for maximum profit
function stockBuySell(price, n) {
// Prices must be given for at least two days
if (n == 1)
return;
// Traverse through given price array
let 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;
// Store the index of minima
let buy = i++;
// 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
let sell = i - 1;
document.write(`Buy on day: ${buy}
Sell on day: ${sell}<br>`);
}
}
// Driver code
// Stock prices on consecutive days
let price = [100, 180, 260, 310, 40, 535, 695];
let n = price.length;
// Function call
stockBuySell(price, n);
// This code is contributed by Potta Lokesh
</script>
C++
#include <iostream>
using namespace std;
// Preprocessing helps the code run faster
#define fl(i, a, b) for (int i = a; i < b; i++)
// Function that return
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
fl(i, 1, size) if (prices[i] > prices[i - 1]) maxProfit
+= prices[i] - prices[i - 1];
return maxProfit;
}
// Driver Function
int main()
{
int prices[] = { 100, 180, 260, 310, 40, 535, 695 };
int N = sizeof(prices) / sizeof(prices[0]);
cout << maxProfit(prices, N) << endl;
return 0;
}
// This code is contributed by Kingshuk Deb
C
// Importing the required header files
#include <stdio.h>
// Creating MACRO for finding the maximum number
#define max(x, y)(((x) > (y)) ? (x) : (y))
// Creating MACRO for finding the minimum number
#define min(x, y)(((x) < (y)) ? (x) : (y))
// Function that return
int maxProfit(int prices[], int size)
{
// maxProfit adds up the difference between
// adjacent elements if they are in increasing order
int ans = 0;
// The loop starts from 1
// as its comparing with the previous
for (int i = 1; i < size; i++)
{
// If the current element is greater than the previous
// then the difference is added to the answer
if (prices[i] > prices[i - 1])
ans += prices[i] - prices[i - 1];
}
return ans;
}
// Driver Code
int main()
{
int price[] = { 100, 180, 260, 310,
40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);
printf("%d", maxProfit(price, n));
return 0;
}
Java
// 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.
Python3
# Python3 program for the above approach def max_profit(prices: list, days: int) -> int: profit = 0 for i in range(1, days): # checks if elements are adjacent and in increasing order if prices[i] > prices[i-1]: # difference added to 'profit' profit += prices[i] - prices[i-1] return profit # Driver Code if __name__ == '__main__': # stock prices on consecutive days prices = [100, 180, 260, 310, 40, 535, 695] # function call profit = max_profit(prices, len(prices)) print(profit) # This code is contributed by vishvofficial.
C#
// C# program for the above approach
using System;
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
Console.WriteLine(maxProfit(price, n));
}
}
// This code is contributed by ukasp
Javascript
<script>
// javascript program for the above approach
function maxProfit(prices , size) {
// maxProfit adds up the difference between
// adjacent elements if they are in increasing order
var maxProfit = 0;
// The loop starts from 1
// as its comparing with the previous
for (i = 1; i < size; i++)
if (prices[i] > prices[i - 1])
maxProfit += prices[i] - prices[i - 1];
return maxProfit;
}
// Driver code
// stock prices on consecutive days
var price = [ 100, 180, 260, 310, 40, 535, 695 ];
var n = price.length;
// function call
document.write(maxProfit(price, n));
// This code is contributed by umadevi9616
</script>
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