题目
链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
**Level: ** Medium
Discription:
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] = 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.
Note:
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
代码一（DP）
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int profit=0;
int hold[50001]={0};//持有股票
int nohold[50001]={0};//不持有股票
hold[0]=-prices[0];
nohold[0]=0;
for(int i=1;i<prices.size();i++)
{
nohold[i]=max(nohold[i-1],hold[i-1]+prices[i]-fee);
hold[i]=max(hold[i-1],nohold[i-1]-prices[i]);
}
return nohold[prices.size()-1];
}
};
思考
- 算法时间复杂度为O((n))，空间复杂度为O((n) )，这里空间复杂度其实可以优化，因为两个max函数中，如果nohold改变了即取了右边的值，hold只会取左边的值（大小关系），则每个状态其实只与前一前一天的状态有关，当天的nohold和hold并不会相互影响，所以可以只用一个变量存放nohold和hold，而不需要用数组。
- 代码一是动态规划的思想。拆分成小问题是每一天的收益，每一天有两种情况，持有股票和不持有股票，它们的收益分别用hold和nohold来表示。
- 当天持有股票的状态有两个可能的原因，一是昨天持有股票今天不变，二是昨天未持有，今天购入，那区分二者用一个max函数，选择收益最大的那种策略。转移方程为hold[i]=max(hold[i-1],nohold[i-1]-prices[i])。
- 当天未持有股票的状态有两个可能的原因，一是昨天未持有股票今天不变，二是昨天持有，今天卖出，那区分二者用一个max函数，选择收益最大的那种策略。转移方程为nohold[i]=max(nohold[i-1],hold[i-1]+prices[i]-fee);。
- 最后一天是不持有股票的，所以输出nohold的最后的值。
代码二（贪心）
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int sell=0;
int buy=0;
int profit=0;
for(int i=0;i<prices.size();i++)
{
if(buy==0)
buy=prices[i];
else
{
if(sell==0)
{
if(prices[i]<buy)
buy=prices[i];
else if(prices[i]-buy>fee)
sell = prices[i];
else
continue;
}
else
{
if(prices[i]<=sell-fee)
{
profit+=sell-buy-fee;
sell=0;
buy=prices[i];
}
else if(prices[i]>sell)
sell=prices[i];
else
continue;
}
}
}
if(sell&&buy)
profit+=sell-buy-fee;
return profit;
}
};
思考
- 算法时间复杂度为O((n))，空间复杂度为O((1) )。
- 代码二是贪心的思想。保证每一笔交易都是最大化收益，关键是卖出的时间点，只当价格低于sell-fee时卖出。