A General Solution to Stock-Trading Problems in Dynamic Programming

The General State-Transition Equations

There is a class of dynamic-programming problems that give you a sequence of stock prices and ask for the maximum profit you can earn by buying and selling. These problems come in many variants — only one transaction allowed, unlimited transactions, an added transaction fee, and so on. In other words, the maximum profit is generally determined by the trading day and the maximum number of transactions allowed (where one transaction is a single buy paired with a single sell).

We can use T[i][k] to denote the maximum profit obtainable at the end of day i with at most k transactions. Furthermore, at the end of day i there are two possible states: holding a stock, T[i][k][1], or not holding a stock, T[i][k][0]. This gives us the following base cases:

T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -Infinity

Here T[-1][k][0] = 0 and T[i][0][0] = 0 mean that in the initial state (i = -1), with no stock, the profit is 0, and when at most 0 transactions are allowed the profit is likewise 0. Meanwhile T[-1][k][1] = T[i][0][1] = -Infinity means that holding a stock in the initial state, or holding a stock when 0 transactions are allowed, is impossible, so its profit is set to -Infinity.

As for the state transitions, we can derive the following equations:

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
// When we hold no stock at the end of day i, there are two possible actions:
// 1. Do nothing — the maximum profit is T[i-1][k][0]
// 2. Sell — the maximum profit on day i is the maximum profit from the previous day while holding a stock, plus that day's selling price: T[i-1][k][1] + prices[i]
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])
// When we hold a stock at the end of day i, there are likewise two possible actions:
// 1. Do nothing — that is T[i-1][k][0]
// 2. Buy — buying adds one transaction, so the maximum number of transactions at the end of day i-1 is k-1, and the maximum profit at the end of the day is T[i-1][k-1][0] - prices[i]

Since the final step in the maximum-profit case should be selling the stock, the value we ultimately return should be T[i][k][0].

Best Time to Buy and Sell Stock This problem asks for the maximum profit when only a single transaction is allowed — the case k = 1. Its solution is as follows:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_i10=0,T_i11=INT_MIN;
        for(int price:prices){
            T_i10=max(T_i10,T_i11+price);
            T_i11=max(T_i11,-price);
        }
        return T_i10;
    }
};

Best Time to Buy and Sell Stock II This problem places no limit on the number of transactions — the case k = Infinity. Here k-1 = k, so the state-transition equations can be written as:

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i]) = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

Because T[i][k][0] is updated in the previous step, we can use a temporary variable to save T[i][k][0]. The code is as follows:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_ik0=0,T_ik1=INT_MIN;
        for(int price:prices){
            int T_ik0_old=T_ik0;
            T_ik0=max(T_ik0,T_ik1+price);
            T_ik1=max(T_ik1,T_ik0_old-price);
        }
        return T_ik0;
    }
};

Best Time to Buy and Sell Stock III This problem asks for the maximum profit when the number of transactions is capped at 2, so k = 2 or k = 1. Similar to the k = 1 case, its state-transition equations can be written as:

T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1] + prices[i])
T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0] - prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], -prices[i])

The optimal value to return is T[i][k][0] = T[i][2][0]. The complete solution is as follows:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_i10=0,T_i11=INT_MIN;
        int T_i20=0,T_i21=INT_MIN;
        for(int price:prices){
            T_i20=max(T_i20,T_i21+price);
            T_i21=max(T_i21,T_i10-price);
            T_i10=max(T_i10,T_i11+price);
            T_i11=max(T_i11,-price);
        }
        return T_i20;
    }
};

Best Time to Buy and Sell Stock IV This problem passes k as a parameter to the solving function. Since every profitable transaction requires two days, once k >= n/2 increasing k further yields no additional profit, so this can be treated as k = Infinity — the same situation as the earlier problem. When k < n/2 it resembles the k = 2 case, and we can update going forward by creating arrays. The solution is as follows:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k>=prices.size()>>1){
            int T_ik0=0,T_ik1=INT_MIN;
            for(int price:prices){
                int T_ik0_old=T_ik0;
                T_ik0=max(T_ik0,T_ik1+price);
                T_ik1=max(T_ik1,T_ik0_old-price);
            }
            return T_ik0;
        }
        vector<int> T_ik0(k+1,0);
        vector<int> T_ik1(k+1,INT_MIN);
        for(int price:prices){
            for(int j=k;j>0;j--){
                T_ik0[j]=max(T_ik0[j],T_ik1[j]+price);
                T_ik1[j]=max(T_ik1[j],T_ik0[j-1]-price);
            }
        }
        return T_ik0[k];
    }
};

Best Time to Buy and Sell Stock with Cooldown This problem places no limit on k — it is Infinity — but adds another constraint: you cannot sell a stock one day and immediately buy again the next day, which acts as a cooldown. In this state-transition equation, the update to T[i][k][1] differs. When we rest on day i it is the same, but when we buy, the update becomes T[i-2][k-1][0] = T[i-2][k][0]. The state-transition equations are:

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0] - prices[i])

The code for this problem is:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_ik0_pre=0,T_ik0=0,T_ik1=INT_MIN;
        for(int price:prices){
            int T_ik0_old=T_ik0;
            T_ik0=max(T_ik0,T_ik1+price);
            T_ik1=max(T_ik1,T_ik0_pre-price);
            T_ik0_pre=T_ik0_old;
        }
        return T_ik0;
    }
};

Best Time to Buy and Sell Stock with Transaction Fee This problem differs from the previous ones in that each transaction incurs a fixed transaction fee, and again there is no limit on the number of transactions. We can subtract the fee amount during each transaction (either when selling or when buying), and then update the corresponding maximum profit T[i][k][0] or T[i][k][1]. The state-transition equations are:

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i] - fee)

or

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i] - fee)
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

The algorithm code is as follows:

#include<climits>
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        long T_ik0=0,T_ik1=LONG_MIN;
        for(int price:prices){
            long T_ik0_old=T_ik0;
            T_ik0=max(T_ik0,T_ik1+price);
            T_ik1=max(T_ik1,T_ik0_old-price-fee);
        }
        return (int)T_ik0;
    }
};

Reference article: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

  • Technology