Search for a command to run...
What it teaches: Two states, with the fee paid on each sale.
Practise it on judges as “Best Time to Buy and Sell Stock with Transaction Fee”.
Unlimited transactions, one share at a time, and each sale costs fee. Return the maximum profit.
Example 1
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8
Constraints
Pattern clues in the wording
These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.
Stuck? Take one hint at a time
class Solution {
public int maxProfit(int[] prices, int fee) {
return 0;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | prices = [1,3,2,8,4,9] fee = 2 | 8 |
| 2 | prices = [1,3,7,5,10,3] fee = 3 | 6 |
From slow to fast
cash (no share) and hold (one share), updated each day.
class Solution {
public int maxProfit(int[] prices, int fee) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
cash = Math.max(cash, hold + prices[i] - fee);
hold = Math.max(hold, cash - prices[i]);
}
return cash;
}
}Verdict: Simple and optimal.
Before you submit
Test these inputs
Mistakes people make
Interview
Why can hold use today's updated cash?