Skip to content

DP On Stocks

Problems discussed

  1. Buy and sell stocks I
  2. Buy and sell stocks II
  3. Buy and sell stocks III
  4. Buy and sell stocks IV
  5. Buy and sell stocks with cooldown
  6. Best Time to Buy and Sell Stock with Transaction Fee

Buy and sell stocks I

Find the problem on leetcode

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the \(i^{\text{th}}\) day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Approach

  • Pretty simple approach we can see for this,
    • We only sell with the minimum buy price to the left.
    • Now we record the max profit possible.

Hence the following code

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_ = INT_MAX;
        int max_profit = INT_MIN;

        for (int i = 0; i < prices.size(); i++) {
            min_ = std::min(min_, prices[i]);
            max_profit = std::max(max_profit, prices[i] - min_);
        }

        return max_profit;
    }
};

Buy and sell stocks II

Find the problem on Leetcode

Problem Statement

Problem statement is same as the last one but here you can buy multiple times (but not before you sell off first). You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

You are given an integer array prices where prices[i] is the price of a given stock on the \(i^{\text{th}}\) day. Find maximum profit possible.

Approach

  • This problem can be solved by greedy strategy, but requires a proof why that works.
  • However we don't need any argument as to why DP based solution is correct, because it explores all possibility of buy and sell choices.
    • If we look closely, we have 4 choices, if we bought previously then we can sell or not sell (2 choices)
    • if we have sold earlier on a given day we have 2 choices (buy or sell).
    • Based on that we write the recurrence and memoize to solve this problem.
  • In the following implementation B is indication for buy order availability and N for not availability.

Code

class Solution {
public:
    int subroutine(vector<int>& prices, int index, char order,
                   map<int, map<char, int>>& dp) {

        if (index >= prices.size()) return 0;

        int profit = 0;

        if (dp.find(index) != dp.end()) {
            if ((*dp.find(index)).second.find(order) != (*dp.find(index)).second.end()) {
                return dp[index][order];
            }
        }

        if (order == 'B') {
            // we can buy now
            dp[index + 1]['N'] = subroutine(prices, index + 1, 'N', dp),
            dp[index + 1]['B'] = subroutine(prices, index + 1, 'B', dp);

            profit = std::max(
                dp[index + 1]['N'] - prices[index], // buy today
                dp[index + 1]['B'] // don't buy
            );
        } else {
            // we have choice to sell
            dp[index + 1]['B'] = subroutine(prices, index + 1, 'B', dp);
            dp[index + 1]['N'] = subroutine(prices, index + 1, 'N', dp);

            profit = std::max(
                prices[index] + dp[index + 1]['B'], // sell today
                dp[index + 1]['N']
            );
        }

        return dp[index][order] = profit;
    }

    int maxProfit(vector<int>& prices) {
        // 'B' enter the day with 'B'(buy) order available. 'N' not available
        map<int, map<char, int>> dp;
        return std::max(subroutine(prices, 0, 'B', dp), 0);
    }
};

Converting the code into tabulation, to reduce recursion space.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 'B' enter the day with 'B'(buy) order available. 'N' not available
        int n = prices.size();
        int dp[n + 1][2];

        // 1 -> buy order available
        // 0 -> buy order not available

        // base cases
        dp[n][1] = 0;
        dp[n][0] = 0;

        for (int index = n - 1; index >= 0; index--) {
            for (int order = 0; order <= 1; order++) {
                int profit = 0;
                if (order == 1) {
                    profit = std::max(
                        dp[index + 1][0] - prices[index], // buy today
                        dp[index + 1][1] // don't buy
                    );
                } else {
                    profit = std::max(
                        prices[index] + dp[index + 1][1], // sell today
                        dp[index + 1][0]
                    );
                }

                dp[index][order] = profit;
            }
        }

        return dp[0][1];
    }
};

Even more optimization

We are using only one index up from the currently exploring index in the dp table. So no need to store index + 1 once we done exploring index for some index \(\in [1, n-1]\). We can replace current index + 1 entries with index entries before we reach index - 1.

Hence we first set dp as a pair<int, int>. Then we say dp.first is same as dp[index + 1][0] and dp.second is same as dp[index + 1][1], then replace dp.first and dp.second accordingly.

class Solution {
public:
    pair<int, int> dp;

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

        // base cases
        dp.first = 0; // same as dp[idx + 1][1]
        dp.second = 0;

        for (int index = n - 1; index >= 0; index--) {
            for (int order = 0; order <= 1; order++) {
                int profit = 0;
                if (order == 1) {
                    profit = std::max(
                        dp.first - prices[index], // buy today
                        dp.second // don't buy
                    );

                    dp.second = profit;
                } else {
                    profit = std::max(
                        prices[index] + dp.second, // sell today
                        dp.first
                    );

                    dp.first = profit;
                }
            }
        }

        return dp.second;
    }
};

Buy and sell stocks III

Find the problem on Leetcode

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the \(i^{\text{th}}\) day.

Find the maximum profit you can achieve. You may complete at most two transactions.

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

Approach

The approach will be pretty much the same but we'll introduce a cap variable in the recursion, whenever a sell happens we can reduce this cap to cap - 1. Then stop the recursion when we reach cap.

Code

class Solution {
public:

    int subroutine(vector<int>& prices, int index, int order,
                   vector<vector<vector<int>>>& dp, int cap) {

        if (cap <= 0) return 0;
        if (index >= prices.size()) return 0;

        int profit = 0;

        if (dp[index][order][cap] != -1) return dp[index][order][cap];

        if (order) {
            // we can buy now
            dp[index + 1][0][cap] = subroutine(prices, index + 1, 0, dp, cap),
            dp[index + 1][1][cap] = subroutine(prices, index + 1, 1, dp, cap);

            profit = std::max(
                dp[index + 1][0][cap] - prices[index], // buy today
                dp[index + 1][1][cap] // don't buy
            );
        } else {
            // we have choice to sell
            dp[index + 1][1][cap - 1] = subroutine(prices, index + 1, 1, dp, cap - 1);
            dp[index + 1][0][cap] = subroutine(prices, index + 1, 0, dp, cap);

            profit = std::max(
                prices[index] + dp[index + 1][1][cap - 1], // sell today
                dp[index + 1][0][cap]
            );
        }

        return dp[index][order][cap] = profit;
    }

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(3, -1)));
        return subroutine(prices, 0, 1, dp, 2);
    }
};

Buy and sell stocks IV

Find the problem on Leetcode

Problem statement

You are given an integer array prices where prices[i] is the price of a given stock on the \(i^{\text{th}}\) day.

Find the maximum profit you can achieve. You may complete at most \(k\) transactions.

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

Approach

Once simple modification we need to do, that is update the initial call from \(2\) to \(k\) and update the cap size in the dp table from \(3\) to \(k + 1\) to accomodate \(0 \dots k\).

Code

class Solution {
public:
    int subroutine(vector<int>& prices, int index, int order,
                   vector<vector<vector<int>>>& dp, int cap) {

        if (cap <= 0) return 0;
        if (index >= prices.size()) return 0;

        int profit = 0;

        if (dp[index][order][cap] != -1) return dp[index][order][cap];

        if (order) {
            // we can buy now
            dp[index + 1][0][cap] = subroutine(prices, index + 1, 0, dp, cap),
            dp[index + 1][1][cap] = subroutine(prices, index + 1, 1, dp, cap);

            profit = std::max(
                dp[index + 1][0][cap] - prices[index], // buy today
                dp[index + 1][1][cap] // don't buy
            );
        } else {
            // we have choice to sell
            dp[index + 1][1][cap - 1] = subroutine(prices, index + 1, 1, dp, cap - 1);
            dp[index + 1][0][cap] = subroutine(prices, index + 1, 0, dp, cap);

            profit = std::max(
                prices[index] + dp[index + 1][1][cap - 1], // sell today
                dp[index + 1][0][cap]
            );
        }

        return dp[index][order][cap] = profit;
    }

    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(k + 1, -1)));
        return subroutine(prices, 0, 1, dp, k);
    }
};

Buy and sell stocks with cooldown

Find the problem on leetcode \(\to\)

Problem Statement

Same as above, 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, same as Buy and sell stocks II) with the following restrictions:

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

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

Approach

We write the same exact code as Buy and sell stocks II and we change the sell to continue from index + 2 because after a sell we go have one day cooldown.

Code

class Solution {
public:
    int subroutine(vector<int>& prices, int index, char order,
                   map<int, map<char, int>>& dp) {

        if (index >= prices.size()) return 0;

        int profit = 0;

        if (dp.find(index) != dp.end()) {
            if ((*dp.find(index)).second.find(order) != (*dp.find(index)).second.end()) {
                return dp[index][order];
            }
        }

        if (order == 'B') {
            // we can buy now
            dp[index + 1]['N'] = subroutine(prices, index + 1, 'N', dp),
            dp[index + 1]['B'] = subroutine(prices, index + 1, 'B', dp);

            profit = std::max(
                dp[index + 1]['N'] - prices[index], // buy today
                dp[index + 1]['B'] // don't buy
            );
        } else {
            // we have choice to sell
            dp[index + 2]['B'] = subroutine(prices, index + 2, 'B', dp);
            dp[index + 1]['N'] = subroutine(prices, index + 1, 'N', dp);

            profit = std::max(
                prices[index] + dp[index + 2]['B'], // sell today
                dp[index + 1]['N']
            );
        }

        return dp[index][order] = profit;
    }

    int maxProfit(vector<int>& prices) {
        // 'B' enter the day with 'B'(buy) order available. 'N' not available
        map<int, map<char, int>> dp;
        return subroutine(prices, 0, 'B', dp);
    }
};

Best Time to Buy and Sell Stock with Transaction Fee

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the \(i^{\text{th}}\) day.

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)

Approach

Same as the Buy and sell stocks II but here we'll pass a new variable called fee, and once a buy is done we subtract fee from profit.

Code

class Solution {
public:
    int subroutine(vector<int>& prices, int index, char order,
                   map<int, map<char, int>>& dp, int fee) {

        if (index >= prices.size()) return 0;

        int profit = 0;

        if (dp.find(index) != dp.end()) {
            if ((*dp.find(index)).second.find(order) != (*dp.find(index)).second.end()) {
                return dp[index][order];
            }
        }

        if (order == 'B') {
            // we can buy now
            dp[index + 1]['N'] = subroutine(prices, index + 1, 'N', dp, fee),
            dp[index + 1]['B'] = subroutine(prices, index + 1, 'B', dp, fee);

            profit = std::max(
                dp[index + 1]['N'] - prices[index] - fee, // buy today, charge fee once the buy is done
                dp[index + 1]['B'] // don't buy
            );
        } else {
            // we have choice to sell
            dp[index + 1]['B'] = subroutine(prices, index + 1, 'B', dp, fee);
            dp[index + 1]['N'] = subroutine(prices, index + 1, 'N', dp, fee);

            profit = std::max(
                prices[index] + dp[index + 1]['B'], // sell today
                dp[index + 1]['N']
            );
        }

        return dp[index][order] = profit;
    }

    int maxProfit(vector<int>& prices, int fee) {
        map<int, map<char, int>> dp;
        return subroutine(prices, 0, 'B', dp, fee);
    }
};

Comments

This comments system is powered by GitHub Discussions