HackMD
714. Best Time to Buy and Sell Stock with Transaction Fee
題目描述
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
範例
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
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
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Constraints:
- 1 <=
prices.length<= 5 * 104 - 1 <=
prices[i]< 5 * 104 - 0 <=
fee< 5 * 104
解答
Python
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
hold, sold = float('-inf'), 0
for price in prices:
hold, sold = max(hold, sold - price), max(sold, hold + price - fee)
return sold
Yen-Chi ChenFri, Jun 23, 2023
C++
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
ios_base::sync_with_stdio(0); cin.tie(0);
int buy = numeric_limits<int>::min();
int sell = 0;
for (int i = 0; i < prices.size(); i ++) {
buy = max(buy, sell - prices[i]);
sell = max(sell, buy + prices[i] - fee);
// cout << prices[i] << " " << buy << " " << sell << endl;
}
return sell;
}
};
Jerry Wu22 June, 2023
Java
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int hold = -prices[0];
int free = 0;
for (int i = 1; i < n; i++) {
int temp_hold = hold;
hold = Math.max(hold, free - prices[i]);
free = Math.max(free, temp_hold + prices[i] - fee);
}
return free;
}
}
Ron ChenFri, Jun 23, 2023
