Learning Outcome
Turn the Two Stock Arrays with Switching Cost interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.
Original Interview Statement
Given daily values for two stocks and a percentage cost to switch, maximize final money.
Examples
| Item | Detail |
|---|---|
| S1=[12,10,17], S2=[5,1,100], cost=8% | DP chooses hold/switch each day |
Brute Force Approach
Try every sequence of stock choices across days.
Optimized Approach
Maintain best money if currently holding stock 1 or stock 2. Transition either stay or switch after applying cost.
Exact Pseudocode
dp1, dp2 = initial holdings
for each day:
next1 = max(stay1, switch2to1)
next2 = max(stay2, switch1to2)
return max(dp1, dp2)Reference Code
def max_money(stock1, stock2, switch_percent):
fee = switch_percent / 100.0
hold1 = float(stock1[0])
hold2 = float(stock2[0])
prev1 = stock1[0]
prev2 = stock2[0]
for a, b in zip(stock1[1:], stock2[1:]):
next1 = max(hold1 * a / prev1, hold2 * (1 - fee) * a / prev2)
next2 = max(hold2 * b / prev2, hold1 * (1 - fee) * b / prev1)
hold1, hold2 = next1, next2
prev1, prev2 = a, b
return max(hold1, hold2)Complexity
| Item | Detail |
|---|---|
| Brute force | O(2^n) |
| Optimized | O(n) time, O(1) space |
Edge Cases
- Zero switching cost
- Very high switching cost
- Equal prices
Follow-ups
- Transaction fee per switch as fixed amount
- Allow cash state
Nearest Practice References
- Best Time to Buy and Sell Stock with Transaction Fee
- State DP
Common Mistakes
- Copying the nearest LeetCode solution without checking the changed rule.
- Skipping duplicate or boundary cases.
- Not stating the brute force before the optimized approach.