Question
Trading with Service Charge
You are given a list of n integers prices, where the value at index i represents the cost of a commodity on day i. You are also given an integer fee, which is the fixed service charge applied to every complete buy–sell cycle.
Your goal is to determine the maximum total profit you can earn by performing any number of buy and sell actions. However, the following rules must be followed:
-
You can hold at most one unit of the commodity at a time. This means you must sell your current holding before making another purchase.
-
Each time you finish a transaction (buy → sell), a service charge (the fee) is deducted from your profit.
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
Output an integer representing the maximum profit that you can achieve.
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.