题目描述
Your are given an array of integers prices
, for which the i
-th element is the price of a given stock on day i
; and a non-negative integer fee
representing a transaction fee.
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
Return the maximum profit you can make.
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] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Note:
0 < prices.length <= 50000
.
0 < prices[i] < 50000
.
0 <= fee < 50000
.
题意:给定一个整数数组prices
,其中第i
个元素代表了第i
天的股票价格 ;非负整数fee
代表了交易股票的手续费用。你可以无限次地完成交易,但是你每次交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
算法1
(贪心) $O(n)$
题解1:贪心:类似于Leetcode 122题,之前那题我们是只要后面的元素大于前面的元素,这一段差值就是我们最终收益的一部分,但是这一题需要收手续费,所以只有当后面的元素减去前面的元素大于fee
的时候,我们才可以卖出。所以整体思路类似,cur_min
代表当前最小值,我们遍历整个数组,如果当前价格小于cur_min
,那么更新最小值,否则如果当前价格比前一天价格加上fee
还要大,那么我们就可以记为答案的一部分,但是这里cur_min
需要更新成prices[i] - fee
。
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size(),cur_min = INT_MAX,res = 0;
for(int i = 0 ; i < n ; i ++)
{
if(prices[i] < cur_min)
cur_min = prices[i];
else if(prices[i] - cur_min > fee)
{
res += prices[i] - cur_min - fee;
cur_min = prices[i] - fee;
}
}
return res;
}
算法2
(动态规划) $O(n)$
题解2:动态规划。
状态表示:hold[i]
代表第i
天持有股票的时候获得的最大收益,unhold[i]
代表第i
天不持有股票的时候获得的最大收益。
状态初始化:hold[0] = -prices[0]
表示第一天买了股票,那我目前的收益应该是负数,unhold[0] = 0
,代表我第一天什么都不做。
状态转移:当我手上持有股票的时候,当前天我可以选择继续持有股票或者卖出股票;当我手上没有股票的时候,当前天我可以选择继续不持有股票或者卖出股票。所以状态转移为:
hold[i] = max(hold[i - 1],unhold[i - 1] - prices[i]);
unhold[i] = max(unhold[i - 1],hold[i - 1] + prices[i] - fee);
答案状态:经过所有交易后,最后一天我们手上是没有股票的,所以答案就是unhold[n - 1]
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size(),hold[n] = {-prices[0]},unhold[n] = {};
for(int i = 1 ; i < n ; i ++)
{
hold[i] = max(hold[i - 1],unhold[i - 1] - prices[i]);
unhold[i] = max(unhold[i - 1],hold[i - 1] + prices[i] - fee);
}
return unhold[n - 1];
}
上面的动态规划初始值hold[0] = -prices[0]
意味着,我们的手续费是在卖出的时候扣除的,如果hold[0] = -prices[i] - fee
的话代表我们的手续费是在买入的时候扣除的,所以下面的题解也为正确答案。
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size(),hold[n] = {-prices[0] - fee},unhold[n] = {};
for(int i = 1 ; i < n ; i ++)
{
hold[i] = max(hold[i - 1],unhold[i - 1] - prices[i] - fee);
unhold[i] = max(unhold[i - 1],hold[i - 1] + prices[i]);
}
return unhold[n - 1];
}
谢谢up主分享,请问第一种算法为什么卖了过后cur_min 要更新成prices[i] - fee 而不是prices[i]呢?
因为手续费已经在第一次累加时扣除了,如果不更新cur_min的话下次更新还会扣除手续费。
其实第一种做法,我不是很推荐,建议把第二种做法弄懂,所有的买股票的题都可以用动态规划的方法解决。每天的状态就是持有股票和不持有股票,状态也只有对应的两种,转移起来非常方便。
好的,多谢up主的解答,赞!