Maximize stock profit with constraints

Given an array prices of daily stock prices, you may make at most two complete transactions (buy then sell). After each sell, there is a mandatory one-day cooldown during which you cannot buy, and each sell incurs a transaction fee fee. Compute the maximum achievable profit in O(n) time and O(1) additional space. Return 0 if no profitable trades exist.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Maximize Stock Profit with Cooldown and Fee

You are given an integer array prices where prices[i] is the price of a given stock on day i, and an integer fee.

You may complete at most two transactions (a transaction is one buy followed later by one sell; you may not hold more than one share at a time, so you must sell before buying again). Two extra rules apply:

1. Cooldown: After you sell on day i, you may not buy on day i + 1 (one mandatory cooldown day). You may buy again on day i + 2 or later.
2. Fee: Each completed sale incurs a transaction fee, subtracted from that sale's proceeds.

Return the maximum profit you can achieve. If no sequence of trades yields a positive profit, return 0.

Your algorithm must run in O(n) time using O(1) additional space.

Constraints

• 0 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4
• 0 <= fee <= 10^4
• At most two complete transactions (buy then sell); you hold at most one share at a time.
• After any sell on day i, buying is forbidden on day i + 1 (one-day cooldown).
• Each completed sale subtracts fee from its proceeds.
• Required: O(n) time and O(1) additional space.
• Return 0 when no profitable sequence of trades exists.

Examples

Example 1

Input: ([3, 3, 5, 0, 0, 3, 1, 4], 0)
Output: 6

Explanation: fee=0. Buy at 0 (day 3), sell at 3 (day 5) -> +3; cooldown day 6, buy at 1 (day 6) is the cooldown day so skip, buy at 1 on day 6 forbidden; instead buy at 0 (day 4) sell at 3 (day 5), then buy at 1 (day 6) sell at 4 (day 7). Best two cooldown-separated trades total 6.

Example 2

Input: ([1, 2, 3, 4, 5], 0)
Output: 4

Explanation: fee=0, strictly increasing. One transaction buy at 1, sell at 5 captures the entire +4 run; splitting it would force a cooldown gap that loses value, so 4 is optimal.

Hints

1. Track four running states as you sweep the prices once: the best profit while holding the 1st share (buy1), after completing the 1st sale (sell1), while holding the 2nd share (buy2), and after the 2nd sale (sell2).
2. The cooldown only matters between the first sale and the second buy. Buy the 2nd share using the value of sell1 from yesterday, not today, so a buy can never sit on the day immediately after a sale.
3. Apply the fee at the moment of each sell: sell transitions use + price - fee. Buy transitions use - price.
4. The answer is max(0, sell1, sell2): zero transactions is always allowed, and one transaction may beat two when the fee or cooldown eats the second trade's margin.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given an array prices of daily stock prices, you may make at most two complete transactions (buy then sell). After each sell, there is a mandatory one-day cooldown during which you cannot buy, and each sell incurs a transaction fee fee. Compute the maximum achievable profit in O(n) time and O(1) additional space. Return 0 if no profitable trades exist.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.