Problem

Submissions

Hints & solutions

Discuss

Best Time to Buy and Sell Stock III

Hard

0/120

Contributed by

151 upvotes

Asked in companies

Problem statement

You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘n’ days.

You are given an array ‘prices’ which such that ‘prices[i]’ denotes the price of the stock on the ith day.

You don't want to do more than 2 transactions. Find the maximum profit that you can earn from these transactions.

Note

1. Buying a stock and then selling it is called one transaction.

2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again.

Example:

Input: ‘n’ = 7, ‘prices’ = [3, 3, 5, 0, 3, 1, 4].

Output: 6

Explanation: 
The maximum profit can be earned by:
Transaction 1: Buying the stock on day 4 (price 0) and then selling it on day 5 (price 3). 
Transaction 2: Buying the stock on day 6 (price 1) and then selling it on day 6 (price 4).
Total profit earned will be (3 - 0) + ( 4 - 1) = 6.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of each test case contains an integer 'n' denoting the number of days. 

The second line of each test case contains 'n' space-separated integers, the array ‘prices’.

Output Format :

For each test case, return an integer denoting the maximum profit.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1:

6
1 3 1 2 4 8

Sample Output 1:

Explanation Of Sample Input 1 :

The maximum profit can be earned by:
Transaction 1: Buying the stock on day 1 (price 1) and then selling it on day 2 (price 3). 
Transaction 2: Buying the stock on day 3 (price 1) and then selling it on day 6 (price 8).
Total profit earned will be (3 - 1) + ( 8 - 1) = 9.

Sample Input 2:

5
5 4 3 2 1

Sample Output 2:

Explanation of Sample Output 2:

It's better not to do any transactions as the stock prices are decreasing.

Expected time complexity:

The expected time complexity is O(n).

Constraints:

1 <= ‘n’ <= 10^6
0 <= ‘prices[i]’ <= 10^3

Where ‘prices[i]’ is the stock price on ith day. 

Time Limit: 1 sec.

Hint 1

Hint 2

Hint 3

Hint 4

Can you do this recursively? Try to solve the problem by solving its subproblems first.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Recursion

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.

Basically, we have to buy the stock at the minimum possible price and sell at the maximum possible price, keeping in mind that we have to sell the stock before buying it again.

Below is the detailed algorithm:

Call a recursive function ‘maxProfitHelper’ by passing four parameters i.e., 'prices’, starting index, number of transactions, and a boolean variable ‘IsBought’. ‘IsBought’ will help us engage in just one transaction at a time. Initially, ‘IsBought’ is false.

maxProfitHelper(‘prices’, ‘index’, ‘trans’, ‘isBought’):

Base Condition: When we are out of days, or the transactions left are 0, return 0 as you can not do anything.
Now we have three options:
- If ‘isBought’ is false:
  - Buy the stock: Recursively find the profit made by the remaining items by setting ‘isBought’ as true and ‘index’ as ‘index’ + 1. Note that buying a stock is a loss of ‘prices[index]’.
- If ‘isBought’ is true:
  - Sell the stock: Recursively find the profit made by the remaining items by decreasing the transactions by 1 and ‘index’ as ‘index’ + 1. Note that selling a stock is a profit of ‘prices[index]’.
- Skip the day, Recursively find the profit made by the remaining items by setting ‘index’ as ‘index’ + 1.
Return the maximum profit obtained by any of the above options.

Time Complexity

O(2 ^ n), where n is the number of days.

We have three options each day; either skip the day, buy on that day or sell on that day. But we can only engage in one transaction at a time, each recursive call ends up in two recursive calls.

Hence the final time complexity will be O(2 ^ n).

Space Complexity

O(n), where n is the number of days.

We are not using any external data structure. Only recursion stack space of O(n) size is used by the algorithm.

Hence the final space complexity will be O(n).

(100% EXP penalty)

Best Time to Buy and Sell Stock III

Rishit Srivastava

Interview problems

lol

Ye harshad mehta ka friend ban jata toh yaha thodi question krta rehta

32 views

0 replies

1 upvote

Vikesh Kumar

Interview problems

C++ || 5 method

Recursive

int solve(int index, bool buy, int limit,vector<int>& prices){
        int n =prices.size();
        int profit =0;
        if(index == n) return 0;
        if(limit == 0) return 0;
        if(buy){
            int buyKaro = (-prices[index] +solve(index+1,0,limit,prices));
            int skip = solve(index+1, 1,limit,prices);
            profit += max(buyKaro, skip);
        }else{
            int sellKaro =(prices[index] +solve(index+1,1,limit-1,prices));
            int skip= solve(index+1, 0,limit,prices);
            profit += max(sellKaro,skip);
        }

        return profit;
}
int maxProfit(vector<int>& prices)
{
    // Write your code here.
    bool buy =1;
    int n=prices.size();
    
    return solve(0,1,2,prices);
}

Memoisation

int solve1(int index, bool buy, int limit,vector<int>& prices,vector< vector <vector<int> > >&dp){
        int n =prices.size();
        
        if(index == n) return 0;
        if(limit == 0) return 0;
        
        if(dp[index][buy][limit] != -1){
            return dp[index][buy][limit];
        }
        
        int profit =0;
        if(buy){
            int buyKaro = (-prices[index] +solve1(index+1,0,limit,prices,dp));
            int skip = solve1(index+1, 1,limit,prices,dp);
            profit += max(buyKaro, skip);
        }else{
            int sellKaro =(prices[index] +solve1(index+1,1,limit-1,prices,dp));
            int skip= solve1(index+1, 0,limit,prices,dp);
            profit += max(sellKaro,skip);
        }

        return dp[index][buy][limit] =profit;
}
int maxProfit(vector<int>& prices)
{
    // Write your code here.
 
    int n=prices.size();
    vector< vector <vector<int> > >dp(n, vector<vector<int>>(2, vector<int>(3,-1) ) );
    return solve1(0,1,2,prices,dp);
 }

Tabulation

int solve2(vector<int>& prices){
    int n=prices.size();

    vector< vector <vector<int> > >dp(n+1, vector<vector<int>>(2, vector<int>(3,0) ) );
    

    for(int index=n-1; index>=0;index--){
        for(int buy=0; buy<=1; buy++){
            for(int limit =1; limit<=2; limit++){
                int profit =0;
                if(buy){
                    int buyKaro = (-prices[index] +dp[index+1][0][limit]);
                    int skip = dp[index+1][1][limit];
                    profit += max(buyKaro, skip);
                }else{
                    int sellKaro =(prices[index] +dp[index+1][1][limit-1]);
                    int skip= dp[index+1][0][limit];
                    profit += max(sellKaro,skip);
                }
                dp[index][buy][limit] =profit;
            }
        }
    }
    return dp[0][1][2];
}
int maxProfit(vector<int>& prices)
{
    // Write your code here.
    return solve2(prices);
}

SC: 0(1)

int solve3(vector<int>& prices){
    int n=prices.size();

    vector< vector<int> >curr (2, vector<int>(3,0) );
    vector< vector<int> >next (2, vector<int>(3,0) );

    for(int index=n-1; index>=0;index--){
        for(int buy=0; buy<=1; buy++){
            for(int limit =1; limit<=2; limit++){
                int profit =0;
                if(buy){
                    int buyKaro = (-prices[index] +next[0][limit]);
                    int skip = next[1][limit];
                    profit += max(buyKaro, skip);
                }else{
                    int sellKaro =(prices[index] +next[1][limit-1]);
                    int skip= next[0][limit];
                    profit += max(sellKaro,skip);
                }
                curr[buy][limit] =profit;
            }
            next =curr;
        }
    }
    return curr[1][2];
}
int maxProfit(vector<int>& prices)
{
    // Write your code here.
    return solve3(prices);
}

Best Method

int maxProfit(vector<int>& prices)
{
    // Write your code here.
    
    buy1, sell1, buy2 and sell2 are profit after frist buy, frist sell, second buy ans second sell respectively.
    
    int buy1 = INT_MIN, sell1 =0;
    int buy2= INT_MIN, sell2 =0;
    
    for(auto price : prices){
        buy1 = max(buy1, -price);
        sell1 =max(sell1,buy1+price);

        buy2 =max(buy2,sell1-price);
        sell2 =max(sell2,buy2+price); 
    }
    return sell2;
    
}

324 views

0 replies

5 upvotes

Interview problems

Short Code no dp used!!

#include<bits/stdc++.h>

int maxProfit(vector<int>& prices)

{

int b1 = -1e9, b2 = -1e9, c1 = 0, c2 = 0;

for(int i = 0; i < prices.size(); i++){

b1 = max(b1, -prices[i]);

c1 = max(c1, prices[i] + b1);

b2 = max(b2, c1 - prices[i]);

c2 = max(c2, b2 + prices[i]);

}

return c2;

}

150 views

0 replies

1 upvote

Ganga Madhukar Piska

Interview problems

Best Time to Buy and Sell Stock III (c++)

int maxProfit(vector<int>& prices)

{

int n = prices.size();

if (n <= 1) return 0;

// Initialize variables to track the maximum profit after each transaction

int buy1 = INT_MIN, sell1 = 0;

int buy2 = INT_MIN, sell2 = 0;

for (int price : prices) {

// buy1 represents the maximum profit after the first buy

buy1 = max(buy1, -price);

// sell1 represents the maximum profit after the first sell

sell1 = max(sell1, buy1 + price);

// buy2 represents the maximum profit after the second buy

buy2 = max(buy2, sell1 - price);

// sell2 represents the maximum profit after the second sell

sell2 = max(sell2, buy2 + price);

}

return sell2;

}

177 views

0 replies

0 upvotes

Biren Amanta

Interview problems

JAVA || DP || MEMOIZATION

import java.util.Arrays;

public class Solution {

    private static int dp[][][];
    public static int maxProfit(int[] prices) {
        // Write your code here.
        dp = new int[prices.length+1][2][2];
        for(int[][] temp: dp){
            for(int[] t :temp) Arrays.fill(t, -1);
        }
        int val = getMax(0, prices, 0, 1);
        return val;
    }
    public static int getMax(int idx,int[] prices,int tansaction,int flag){
        if(idx == prices.length) return 0;
        if(tansaction >= 2) return 0;
        if(dp[idx][tansaction][flag] != -1) return dp[idx][tansaction][flag];
        if(flag == 1){
            return dp[idx][tansaction][flag] = Math.max(getMax(idx+1, prices, tansaction, flag),
                -prices[idx] + getMax(idx+1, prices, tansaction, 1-flag));
        }else{
            return dp[idx][tansaction][flag] =  Math.max(getMax(idx+1, prices, tansaction,  flag),
                prices[idx] + getMax(idx+1, prices, tansaction+1, 1-flag));
        }
    }
}

124 views

0 replies

0 upvotes

Sumit Tupe

Interview problems

C++ || Recursion || DP

// with recursion
int rec(vector<int> val, int ind,int buy, int cap,int n)
{
    if(ind>=n || cap<=0) return 0;
    if(buy)
    {
        return max(-val[ind]+rec(val,ind+1,0,cap,n),rec(val, ind+1,1,cap,n));
    }
    else
    {
        return max(val[ind]+rec(val,ind+1,1,cap-1,n),rec(val, ind+1,0,cap,n));

    }
}

// with DP
int withdp(vector<int> val, int cap, int n)
{
    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(2,vector<int>(3,0)));
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<=1;j++)
        {
            for(int c = 1;c<=2;c++)
            {
                if(j==0)
                {
                    dp[i][j][c] = max(-val[i]+dp[i+1][1][c],dp[i+1][0][c]);
                }
                else {
                    dp[i][j][c] = max(+val[i]+dp[i+1][0][c-1],dp[i+1][1][c]);
                }
            }
        }
    }
    return dp[0][0][2];
}

int maxProfit(vector<int>& prices)
{
    return withdp(prices,2,prices.size());   
}

320 views

0 replies

0 upvotes

Ambika Kumar Kewat

Interview problems

Best Time to Buy and Sell Stock III || Memoization || Tabulation || Space optimization

#include <bits/stdc++.h>

// int memo(int ind,int buy,int cap,vector<int>&values,int n,vector<vector<vector<int>>>&dp){

// //base case

// if(ind==n||cap==0){

// return 0;

// }

// if(dp[ind][buy][cap]!=-1){

// return dp[ind][buy][cap];

// }

// if(buy==1){

// return dp[ind][buy][cap]=max(0+memo(ind+1,1,cap,values,n,dp),

// -values[ind]+memo(ind+1,0,cap,values,n,dp));

// }

// return dp[ind][buy][cap]=max(0+memo(ind+1,0,cap,values,n,dp),

// values[ind]+memo(ind+1,1,cap-1,values,n,dp));

// }

int maxProfit(vector<int>& values)

{

int n=values.size();

// vector<vector<vector<int>>>dp(n,vector<vector<int>>(2,vector<int>(3,-1)));

// if(n==0){

// return 0;

// }

// long ans=memo(0,1,2,values,n,dp);

// return ans;

//tabulation

// vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(2,vector<int>(3,0)));

// for(int ind=n-1;ind>=0;ind--){

// for(int buy=0;buy<=1;buy++){

// for(int cap=1;cap<=2;cap++){

// if(buy==1){

// dp[ind][buy][cap]=max(0+dp[ind+1][1][cap],-values[ind]+dp[ind+1][0][cap]);

// }else{

// dp[ind][buy][cap]=max(0+dp[ind+1][0][cap],values[ind]+dp[ind+1][1][cap-1]);

// }

// return dp[0][1][2];

//space optimization

vector<vector<int>>after(2,vector<int>(3,0));

vector<vector<int>>cur(2,vector<int>(3,0));

for(int ind=n-1;ind>=0;ind--){

for(int buy=0;buy<=1;buy++){

for(int cap=1;cap<=2;cap++){

if(buy==1){

cur[buy][cap]=max(0+after[1][cap],-values[ind]+after[0][cap]);

}else{

cur[buy][cap]=max(0+after[0][cap],values[ind]+after[1][cap-1]);

}

after=cur;

}

return after[1][2];

}

349 views

0 replies

1 upvote

Rahul

Interview problems

Best Time to Buy and Sell Stock III

from typing import List


def maxProfit(prices: List[int]) -> int:


    n = len(prices)
    if n <= 1:
        return 0


    # Initialize variables to track maximum profit after each transaction
    max_profit_after_first_trade = [0] * n
    max_profit_after_second_trade = [0] * n


    # Track the minimum price encountered so far
    min_price = prices[0]


    # Calculate maximum profit after the first transaction for each day
    for i in range(1, n):
        max_profit_after_first_trade[i] = max(max_profit_after_first_trade[i - 1], prices[i] - min_price)
        min_price = min(min_price, prices[i])


    # Track the maximum price encountered so far
    max_price = prices[n - 1]


    # Calculate maximum profit after the second transaction for each day
    for i in range(n - 2, -1, -1):
        max_profit_after_second_trade[i] = max(max_profit_after_second_trade[i + 1], max_price - prices[i])
        max_price = max(max_price, prices[i])


    # Calculate the maximum total profit by finding the maximum sum of profits
    max_profit = 0
    for i in range(n):
        max_profit = max(max_profit, max_profit_after_first_trade[i] + max_profit_after_second_trade[i])


    return max_profit

python

106 views

0 replies

1 upvote

Himanshu Verma

Interview problems

MEMOISATION TO TABULATION

import java.util.*;
public class Solution {
    public static int maxProfit(int[] p) {
        // Write your code here.
        int [][]cur=new int[2][3];
        int [][]after=new int[2][3];
        for(int i=p.length-1;i>=0;i--)
        {
            for(int j=0;j<=1;j++){
                for(int cap=1;cap<=2;cap++){
                    if(j==1){
                        cur[j][cap]=Math.max(after[0][cap]-p[i],after[1][cap]);
                    }
                    else{
                        cur[j][cap]=Math.max(after[1][cap-1]+p[i],after[0][cap]);
                    }
                }
                
            }
            after=cur;
        }
        return after[1][2];

    
        //return dowork(p,0,2,0,dp);
    }
    public static int dowork(int []p,int buy,int cap,int ind,int [][][]dp)
    {
        if(cap==0||ind>=p.length){
            return 0;
        }
        if(dp[ind][buy][cap]!=-1){
            return dp[ind][buy][cap];
        }
        int ans=Integer.MIN_VALUE;
        if(buy==0){
            ans=Math.max(dowork(p,1,cap,ind+1,dp)-p[ind],dowork(p,0,cap,ind+1,dp));
        }
        else{
            ans=Math.max(dowork(p,0,cap-1,ind+1,dp)+p[ind],dowork(p,1,cap,ind+1,dp));
        }
        return dp[ind][buy][cap]=ans;

    }
}

147 views

0 replies

0 upvotes

Sonu Kumar

Interview problems

Tabulation

public static int maxProfit(int[] prices) {

// Write your code here.

int[][][]dp=new int[prices.length+1][2][3];

int n=prices.length;

for(int ind=n-1;ind>=0;ind--){

for(int buy=0;buy<=1;buy++){

for(int cap=1;cap<=2;cap++){

if(buy==1){

dp[ind][buy][cap]=Math.max(-prices[ind]+dp[ind+1][0][cap], dp[ind+1][1][cap]);

}

else dp[ind][buy][cap]=Math.max(prices[ind]+dp[ind+1][1][cap-1], dp[ind+1][0][cap]);

}

return dp[0][1][2];

}

195 views

1 reply

0 upvotes

Console