Best Time to Buy and Sell Stock using Recursion and Memoization
We can define a recursive function maxProfit(idx, canSell) which will return us the maximum profit if the user can buy or sell starting from idx.
- If idx == N, then return 0 as we have reached the end of the array
- If canSell == false, then we can only buy at this index. So, we can explore both the choices and return the maximum:
- buy at the current price, so the profit will be: -prices[idx] + maxProfit(idx+1, true)
- move forward without buying, so the profit will be: maxProfit(idx+1, false)
- If canSell == true, then we can only sell at this index. So, we can explore both the choices and return the maximum:
- sell at the current price, so the profit will be: prices[idx]
- move forward without selling, so the profit will be: maxProfit(idx+1, true)
Below is the implementation of the approach:
#include <bits/stdc++.h>
using namespace std;
// function to calculate the max profit
int maxProfit(int idx, vector<int>& prices, bool canSell)
{
// We have reached the end of array
if (idx == prices.size())
return 0;
if (canSell) {
// We can only sell the stock
return max(prices[idx],
maxProfit(idx + 1, prices, canSell));
}
else {
// We can only buy the stock
return max(-prices[idx]
+ maxProfit(idx + 1, prices, true),
maxProfit(idx + 1, prices, canSell));
}
}
int main()
{
vector<int> prices{ 7, 1, 5, 3, 6, 4 };
cout << maxProfit(0, prices, false) << "\n";
return 0;
}
// Java code of the above approach
import java.util.*;
public class GFG {
// Function to calculate the max profit
static int maxProfit(int idx, List<Integer> prices,
boolean canSell)
{
// We have reached the end of the array
if (idx == prices.size())
return 0;
if (canSell) {
// We can only sell the stock
return Math.max(
prices.get(idx),
maxProfit(idx + 1, prices, canSell));
}
else {
// We can only buy the stock
return Math.max(
-prices.get(idx)
+ maxProfit(idx + 1, prices, true),
maxProfit(idx + 1, prices, canSell));
}
}
public static void main(String[] args)
{
List<Integer> prices = new ArrayList<>(
Arrays.asList(7, 1, 5, 3, 6, 4));
System.out.println(maxProfit(0, prices, false));
}
}
// This code is contributed by Susobhan Akhuli
# Python code of the above approach
# Function to calculate the max profit
def max_profit(idx, prices, can_sell):
# We have reached the end of array
if idx == len(prices):
return 0
if can_sell:
# We can only sell the stock
return max(prices[idx], max_profit(idx + 1, prices, can_sell))
else:
# We can only buy the stock
return max(-prices[idx] + max_profit(idx + 1, prices, True),
max_profit(idx + 1, prices, can_sell))
if __name__ == "__main__":
prices = [7, 1, 5, 3, 6, 4]
print(max_profit(0, prices, False))
# This code is contributed by Susobhan Akhuli
// C# Implementation
using System;
using System.Collections.Generic;
public class Program
{
public static int MaxProfit(int idx, List<int> prices, bool canSell)
{
// We have reached the end of the list
if (idx == prices.Count)
return 0;
if (canSell)
{
// We can only sell the stock
return Math.Max(prices[idx], MaxProfit(idx + 1, prices, canSell));
}
else
{
// We can only buy the stock
return Math.Max(-prices[idx] + MaxProfit(idx + 1, prices, true), MaxProfit(idx + 1, prices, canSell));
}
}
public static void Main(string[] args)
{
List<int> prices = new List<int> { 7, 1, 5, 3, 6, 4 };
Console.WriteLine(MaxProfit(0, prices, false));
}
}
// This code is contributed by Sakshi
// JavaScript program for the above approach
// Function to calculate the max profit
function maxProfit(idx, prices, canSell) {
// We have reached the end of the array
if (idx === prices.length) {
return 0;
}
if (canSell) {
// We can only sell the stock
return Math.max(prices[idx], maxProfit(idx + 1, prices, canSell));
} else {
// We can only buy the stock
return Math.max(
-prices[idx] + maxProfit(idx + 1, prices, true),
maxProfit(idx + 1, prices, canSell)
);
}
}
// Driver code
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(0, prices, false)); // Output the max profit
// This code is contributed by Susobhan Akhuli
Output
5
Time Complexity: O(2n), where n is the size of input array prices[]
Auxiliary Space: O(N)
Best Time to Buy and Sell Stock (at most one transaction allowed)
Given an array prices[] of length N, representing the prices of the stocks on different days, the task is to find the maximum profit possible by buying and selling the stocks on different days when at most one transaction is allowed.
Note: Stock must be bought before being sold.
Examples:
Input: prices[] = {7, 1, 5, 3, 6, 4}
Output: 5
Explanation:
The lowest price of the stock is on the 2nd day, i.e. price = 1. Starting from the 2nd day, the highest price of the stock is witnessed on the 5th day, i.e. price = 6.
Therefore, maximum possible profit = 6 – 1 = 5.Input: prices[] = {7, 6, 4, 3, 1}
Output: 0
Explanation: Since the array is in decreasing order, no possible way exists to solve the problem.