class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
}
};
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
提示：
1 <= prices.length <= 5 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104相似题目
原站题解
javascript 解法, 执行用时: 80 ms, 内存消耗: 48.9 MB, 提交时间: 2023-10-07 07:39:01
/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function (prices, fee) {
let f0 = 0, f1 = -Infinity;
for (const p of prices) {
[f0, f1] = [Math.max(f0, f1 + p - fee), Math.max(f1, f0 - p)];
}
return f0;
};
cpp 解法, 执行用时: 76 ms, 内存消耗: 54.1 MB, 提交时间: 2023-10-07 07:38:48
class Solution {
public:
int maxProfit(vector<int> &prices, int fee) {
int f0 = 0, f1 = INT_MIN / 2;
for (int p: prices) {
int new_f0 = max(f0, f1 + p - fee);
f1 = max(f1, f0 - p);
f0 = new_f0;
}
return f0;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 53.3 MB, 提交时间: 2023-10-07 07:38:37
class Solution {
public int maxProfit(int[] prices, int fee) {
int f0 = 0, f1 = Integer.MIN_VALUE / 2;
for (int p : prices) {
int newF0 = Math.max(f0, f1 + p - fee);
f1 = Math.max(f1, f0 - p);
f0 = newF0;
}
return f0;
}
}
python3 解法, 执行用时: 156 ms, 内存消耗: 23 MB, 提交时间: 2023-10-07 07:38:22
class Solution:
def maxProfit1(self, prices: List[int], fee: int) -> int:
n = len(prices)
@cache # 缓存装饰器，避免重复计算 dfs 的结果
def dfs(i: int, hold: bool) -> int:
if i < 0:
return -inf if hold else 0
if hold:
return max(dfs(i - 1, True), dfs(i - 1, False) - prices[i])
return max(dfs(i - 1, False), dfs(i - 1, True) + prices[i] - fee)
return dfs(n - 1, False)
def maxProfit2(self, prices: List[int], fee: int) -> int:
n = len(prices)
f = [[0] * 2 for _ in range(n + 1)]
f[0][1] = -inf
for i, p in enumerate(prices):
f[i + 1][0] = max(f[i][0], f[i][1] + p - fee)
f[i + 1][1] = max(f[i][1], f[i][0] - p)
return f[n][0]
def maxProfit(self, prices: List[int], fee: int) -> int:
f0, f1 = 0, -inf
for p in prices:
f0, f1 = max(f0, f1 + p - fee), max(f1, f0 - p)
return f0
rust 解法, 执行用时: 8 ms, 内存消耗: 2.9 MB, 提交时间: 2023-10-07 07:37:31
impl Solution {
// 递归 + 记忆
pub fn max_profit1(prices: Vec<i32>, fee: i32) -> i32 {
let n = prices.len();
let mut memo = vec![vec![-1; 2]; n]; // -1 表示还没有计算过
fn dfs(idx: i32, hold: bool, prices: &Vec<i32>, memo: &mut Vec<Vec<i32>>, fee: i32) -> i32 {
if idx < 0 {
if hold {
return i32::MIN / 2; // 防止溢出
}
return 0;
}
let i = idx as usize;
let j = hold as usize;
if memo[i][j] != -1 { // 之前计算过
return memo[i][j];
}
let res;
if hold {
res = dfs(idx - 1, true, prices, memo, fee).max(dfs(idx - 1, false, prices, memo, fee) - prices[i]);
} else {
res = dfs(idx - 1, false, prices, memo, fee).max(dfs(idx - 1, true, prices, memo, fee) + prices[i] - fee);
}
memo[i][j] = res; // 记忆化
res
}
dfs(n as i32 - 1, false, &prices, &mut memo, fee)
}
// 递推
pub fn max_profit2(prices: Vec<i32>, fee: i32) -> i32 {
let n = prices.len();
let mut f = vec![(0, 0); n + 1];
f[0].1 = i32::MIN / 2;
for (i, &p) in prices.iter().enumerate() {
f[i + 1].0 = f[i].0.max(f[i].1 + p - fee);
f[i + 1].1 = f[i].1.max(f[i].0 - p);
}
f[n].0
}
pub fn max_profit(prices: Vec<i32>, fee: i32) -> i32 {
let mut f0 = 0;
let mut f1 = i32::MIN / 2;
for p in &prices {
let new_f0 = f0.max(f1 + p - fee);
f1 = f1.max(f0 - p);
f0 = new_f0;
}
f0
}
}
golang 解法, 执行用时: 84 ms, 内存消耗: 7.9 MB, 提交时间: 2021-07-23 10:49:28
func maxProfit(prices []int, fee int) int {
n := len(prices)
sell, buy := 0, prices[0]
for i := 1; i < n; i++ {
sell = max(sell, prices[i]-buy-fee)
buy = min(buy, prices[i]-sell)
}
return sell
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x > y {
return y
}
return x
}