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).
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: - Buying at prices[0] = 1 - Selling at prices[3] = 8 - Buying at prices[4] = 4 - Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3 Output: 6
Constraints:
1 < prices.length <= 5 * 1040 < prices[i], fee < 5 * 104
Related Topics:
Array, Dynamic Programming, Greedy
Similar Questions:
See my following notes for some reference:
- 123. Best Time to Buy and Sell Stock III (Hard)
- 188. Best Time to Buy and Sell Stock IV (Hard)
- 714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)
Let dp[i + 1] be the max profit on i-th day.
If we don't trade on i-th day, dp[i + 1] = dp[i].
Otherwise, we buy on some j-th day (j in [0, i]) and sell on i-th day:
dp[i + 1] = max(prices[i] - prices[j] - fee + dp[j] | 0 <= j <= i)
= prices[i] - fee + max(dp[j] - prices[i] | 0 <= j <= i)
We can define buy[i] = max(dp[j] - prices[i] | 0 <= j <= i), thus:
buy[i] = max(buy[i-1], dp[i] - prices[i]) where i >= 0
buy[-1] = -INF
In this way we can save the computation for getting buy[i].
dp[i + 1] = max(
dp[i],
prices[i] - fee + buy[i]
)
buy[i] = max(buy[i-1], dp[i] - prices[i]) where i >= 0
buy[-1] = -INF
// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int maxProfit(vector<int>& A, int fee) {
if (A.empty()) return 0;
int N = A.size(), buy = INT_MIN;
vector<int> dp(N + 1);
for (int i = 0; i < N; ++i) {
buy = max(buy, dp[i] - A[i]);
dp[i + 1] = max(dp[i], A[i] - fee + buy);
}
return dp[N];
}
};Since dp[i + 1] is only dependent on dp[i], we can use single variable sell to keep track of it.
// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxProfit(vector<int>& A, int fee) {
if (A.empty()) return 0;
int buy = INT_MIN, sell = 0;
for (int n : A) {
buy = max(buy, sell - n);
sell = max(sell, n - fee + buy);
}
return sell;
}
};Another easier way of thinking about this problem:
On day i, we have two options: buy or sell.
If we buy, we must buy based on the maximum possible sell result we can get within [0, i) days. So buy[i] = max( sell[j] | 0 <= j < i ) - prices[i].
If we sell, we must sell based on the maximum possible buy result we can get within [0, i) days. So sell[i] = max( buy[j] | 0 <= j < i ) + prices[i] - fee.
We can memoize the maximum of buy and sell values within day [0, i), and use them to generate the new buy and sell values on day i.
Since buy could result in a negative balance, we should use -INF as the initial value for buy.
Since we won't ever want a negative balance from sell, we should use 0 as the initial value for sell.
// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int maxProfit(vector<int>& A, int fee) {
long buy = INT_MIN, sell = 0;
for (int n : A) {
long buy2 = max(buy, sell - n);
long sell2 = max(sell, buy + n - fee);
buy = buy2;
sell = sell2;
}
return sell;
}
};According to Solution 2, we can merge buy2 and sell2 with buy and sell respectively with no issue. This is because buying and selling on the same day is the same as not trading on day i, whose result should be captured already in buy and sell.