Best Time to Buy and Sell Stock II (infinite transactions allowed)
The cost of a stock on each day is given in an array. Find the maximum profit that you can make by buying and selling on those days. If the given array of prices is sorted in decreasing order, then profit cannot be earned at all.
Examples:
Input: arr[] = {100, 180, 260, 310, 40, 535, 695}
Output: 865
Explanation: Buy the stock on day 0 and sell it on day 3 => 310 – 100 = 210
Buy the stock on day 4 and sell it on day 6 => 695 – 40 = 655
Maximum Profit = 210 + 655 = 865Input: arr[] = {4, 2, 2, 2, 4}
Output: 2
Explanation: Buy the stock on day 4 and sell it on day 5 => 4 – 2 = 2
Maximum Profit = 2
A simple approach is to try buying the stocks and selling them every single day when profitable and keep updating the maximum profit so far.
Follow the steps below to solve the problem:
- Try to buy every stock from start to end – 1
- After that again call the maxProfit function to calculate answer
- curr_profit = price[j] – price[i] + maxProfit(start, i – 1) + maxProfit(j + 1, end)
- profit = max(profit, curr_profit)
Below is the implementation of the above approach:
// 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;
}
// 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 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 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# 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
<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>
Output
865
Time Taken: Very high as we have two nested loops and two recursive calls inside the inner loop.
Stock Buy Sell to Maximize Profit using Local Maximum and Local Minimum:
If we are allowed to buy and sell only once, then we can use the algorithm discussed in maximum difference between two elements. Here we are allowed to buy and sell multiple times.
Follow the steps below to solve the problem:
- Find the local minima and store it as starting index. If it does not exists, return.
- Find the local maxima. And store it as an ending index. If we reach the end, set the end as the ending index.
- Update the solution (Increment count of buy-sell pairs)
- Repeat the above steps if the end is not reached.
Below is the implementation of the above approach:
// 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
// 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;
}
// 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 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# 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
<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>
Output
Buy on day: 0 Sell on day: 3 Buy on day: 4 Sell on day: 6
Time Complexity: O(N), The outer loop runs till I become n-1. The inner two loops increment the value of I in every iteration.
Auxiliary Space: O(1)
Stock Buy Sell to Maximize Profit using Valley Peak Approach:
In this approach, we just need to find the next greater element and subtract it from the current element so that the difference keeps increasing until we reach a minimum. If the sequence is a decreasing sequence, so the maximum profit possible is 0.
Follow the steps below to solve the problem:
- maxProfit = 0
- if price[i] > price[i – 1]
- maxProfit = maxProfit + price[i] – price[i – 1]
Below is the implementation of the above approach:
#include <iostream>
using namespace std;
// 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
for (int i=1; i<size; i++)
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
// 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 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 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# 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
<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>
Output
865
Time Complexity: O(N), Traversing over the array of size N.
Auxiliary Space: O(1)
Contact Us