Question
Maximum Profit with Transaction Fee
You are given an array prices of length n, where prices[i] represents the stock price on the i-th day.
You are also given an integer fee, which denotes the fixed transaction cost for completing a buy–sell operation.
Your task is to determine the maximum profit you can earn by trading the stock over the given days.
You may perform multiple buy and sell operations, subject to the following rules:
-
You can hold at most one stock at a time.
-
You must sell the current stock before buying again.
-
The transaction fee is applied once per buy–sell transaction.
Input
The first line of the input contains a single integer n, representing the size of the array prices.
The second line of the input contains n space separated integers representing elements of the array prices.
The third line contains an integer fee.
The second line of the input contains n space separated integers representing elements of the array prices.
The third line contains an integer fee.
Output
Print a single integer representing the maximum profit achievable.
Example
Sample Input
6
1 3 2 8 4 9
2
Sample output
8
Explanation
The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
Total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
6
1 3 2 8 4 9
2
Sample output
8
Explanation
The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
Total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.