Best time to Buy and Sell Stocks - A comprehensive Guide Part 2

Best time to buy and sell stocks is one of the most popular type of problem series.

In the last article, we learnt about the first four problems of this series. Check it out here.

Now let's learn about the remaining two problems.

We will approach both problems with iterative dynamic programming method. Let us see how.

Best Time to Buy and Sell Stock with Transaction Fee

Leetcode Problem: 714

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

This is similar to problem II wherein we were allowed to buy and sell any number of times that we liked. The only add on is that now every time we make a transaction, we have to pay given fee. Now we have to find the maximum possible profit.

Approach:

1) Traverse prices from left to right.

2) For any given day, we have basically two possible situations : we either have stock at hand or we don't. Create two variables for these two situations, best_with_stock and best_without_stock.

3) For any i, if we have stock, it means that either we had bought a stock on some previous day and have still decided to not sell it. Else it means that we have bought today's stock, i.e., we subtract the current value of stock (which we buy today) from our profit (best_without_stock). Store the maximum value from these two scenario in best_with_stock.

4) For any i, if we don't have a stock, it means that either we approached this day empty handed and still don't buy the current stock. Else it means we had a stock when we approached this day and decided to sell it today. After selling we have to pay fee also as one transaction of buy-sell gets completed. Store the maximum value from these two scenario in best_without_stock.

5) best_without_stock is our final profit. Return it.

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {

        int best_with_stock = -prices[0], best_without_stock=0;

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

            best_without_stock = max(best_without_stock, best_with_stock + prices[i] - fee);
            best_with_stock = max(best_with_stock, best_without_stock - prices[i]);
        }


        return best_without_stock;
    }
};

Todo - Try using this approach in problem II . In the last article, we discussed peak-valley approach solution for this.

Best Time to Buy and Sell Stock with Cooldown

Leetcode Problem: 309

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Here also, we are allowed to make as many transactions as we like. But after selling a stock, we take a break (cooldown) the next day where we cannot buy or sell.

Approach :

1) Traverse prices from left to right.

2) For any given day, we again have two possible situations : we either have stock at hand or we don't.

3) If I have a stock today, it either means that I had a stock when the day came. i.e. best price with stock = best price with stock yesterday. Else, I decide to buy a stock today after cooldown, i.e. we subtract today's price of stock (that we buy) from our profit the day before yesterday (since yesterday was cooldown). best_with_stock = max(best_with_stock_yest, best_without_stock_day_before_yest-prices[i])

4) If I don't have a stock today, either I did not have a stock when I came to this day and decide not to buy today, i.e. best price without stock = best price without stock yesterday. Else, I decide to sell today. best_without_stock = max(best_without_stock_yest, best_with_stock_yest + prices[i]);

5) Return our final profit best_without_stock.

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int best_with_stock = 0;
        int best_without_stock=0;
        int best_without_stock_yest =0;
        int best_with_stock_yest =-prices[0];
        int best_without_stock_day_before_yest = 0;

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

            best_without_stock = max(best_without_stock_yest, best_with_stock_yest + prices[i]);
            best_with_stock = max(best_with_stock_yest, best_without_stock_day_before_yest-prices[i]);

            best_without_stock_day_before_yest = best_without_stock_yest;
            best_with_stock_yest = best_with_stock;
            best_without_stock_yest = best_without_stock;
        }

        return best_without_stock;
    }
};