Maximum Profit from Normal and Short Transactions
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Maximum Profit from Normal and Short Transactions
You are given daily stock prices in `prices` and a positive integer `k`. Complete at most `k` transactions. Each transaction is one of:
- **Normal:** buy on day `i`, then sell on a later day `j`, earning `prices[j] - prices[i]`.
- **Short:** sell on day `i`, then buy back on a later day `j`, earning `prices[i] - prices[j]`.
Only one transaction may be running at a time. A transaction must finish before another starts, and its closing day cannot also be the opening day of the next transaction. The next transaction may start on the following day or any later day.
Return the maximum total profit from completed transactions. Completing fewer than `k` transactions, including none, is allowed.
### C++ Interface
```cpp
class Solution {
public:
long long maximumProfit(vector<int>& prices, int k);
};
```
### Examples
**Example 1**
```text
prices = [2,8,7,1]
k = 2
Output: 12
```
A normal transaction from day zero to day one earns six. A short transaction from day two to day three earns another six. A single transaction earns at most seven. Two transactions need four distinct action days, so with this input they must use day pairs `(0,1)` and `(2,3)`; their maximum combined profit is twelve.
**Example 2**
```text
prices = [1,9,1,1]
k = 2
Output: 8
```
Buying on day zero and selling on day one earns eight. Reusing day one to open a short transaction is forbidden. Two legal transactions would have to use `(0,1)` and `(2,3)`, whose best profits are eight and zero. A single transaction also earns at most eight.
### Constraints
- `2 <= prices.length <= 1000`.
- `1 <= prices[i] <= 1000000000`.
- `1 <= k <= floor(prices.length / 2)`.
- Each transaction uses two strictly ordered days, and successive transactions cannot share an action day.
### Clarifying Questions
- Can a transaction open and close on the same day? No. Its closing day must be later.
- Can one transaction close and the next open on that same day? No, even if they have different types.
- Is there an additional full-day waiting period after closing? No. Starting on the immediately following day is allowed.
- Must exactly `k` transactions be completed? No. The limit is at most `k`.
- Is the cash received when opening a short transaction already its completed profit? No. The later buy-back cost must also be included.
### What a Strong Answer Covers
- Both profit definitions and the prohibition on overlapping or shared-day transactions.
- A maximum over completed transactions, allowing fewer than `k`.
- Correct treatment of unchanged prices and both increasing and decreasing price sequences.
- Correct arithmetic for prices up to one billion and up to 500 completed transactions.
### Follow-up Questions
- What is the best profit when all listed prices are equal?
- How does allowing short transactions change the possibilities on a strictly decreasing price sequence?
```hint Track the end-of-day position
For each completed-transaction count, track the best balance with no open transaction, an open normal transaction, or an open short transaction. Compute all transitions for one day from the previous day's arrays so one action cannot feed another action on the same day.
```
Overview: Maximize profit from at most k completed normal or short stock transactions. Transactions cannot overlap or share a closing and opening day, and the result may require a 64-bit integer.