#6Airline Ticket Reselling — Fare Opportunity Planning
You are analyzing airline ticket prices over a sequence of days. fares[i] represents the market price of an airline ticket on day i.
You may perform at most two buy-and-resell transactions to maximize your total gain. Each transaction consists of: Purchasing a ticket at a lower fare. Reselling it on a later day at a higher fare.
You must complete the first transaction before starting the second one. You cannot hold multiple tickets at the same time. You may choose to make: No transaction One transaction Two transactions
Return the maximum total gain that can be obtained. If no profitable transaction is possible, return 0.
Examples
Example 1
Input: fares = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy at fare 0 and resell at 3, gaining 3. Then buy at 1 and resell at 4, gaining another 3. Total gain = 6.
Example 2
Input: fares = [1,2,3,4,5]
Output: 4
Explanation: Buy at 1 and resell at 5. This produces a gain of 4. A second transaction cannot improve the result.
Example 3
Input: fares = [7,6,4,3,1]
Output: 0
Explanation: Fares continuously decrease, so there is no profitable resale opportunity.
Constraints
- 1 <= fares.length <= 100000
- 0 <= fares[i] <= 1000000
- Each fare is an integer.
- The maximum answer fits within a 32-bit signed integer.
- Fractional fares are not allowed.
- Transaction fees are not included.
- The second purchase can happen only after the first sale.