题目原文
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.
题意分析
给定一组某一stock在每一天的价格,买卖次数不限,每次买入必须在卖出之后,且每次卖出时都需要fee的手续费,求解最大的收益。
解法分析 from here
本题采用两种方法解
动态规划
贪心算法
动态规划
对于第i天的最大收益,应分成两种情况,一是该天结束后手里没有stock,可能是保持前一天的状态也可能是今天卖出了,此时令收益为cash;二是该天结束后手中有一个stock,可能是保持前一天的状态,也可能是今天买入了,用hold表示。由于第i天的情况只和i-1天有关,所以用两个变量cash和hold就可以,不需要用数组。C++代码如下:
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int cash=0;//the maxPro you have if you don't have a stock that day
int hold=-prices[0];//the maxPro you have if you have a stock that day, if you have a stock
// the first day,hold=-prices[0]
int i;
for(i=1;i<prices.size();i++){
cash=max(cash,hold+prices[i]-fee);//cash in day i is the maxvalue of cash in day i-1 or you //sell your stock
hold=max(hold,cash-prices[i]);
}
return cash;
}
};
这里需要注意cash和hold的初始值,最终输出cash,因为最后一天的情况一定是手里没有stock的。
贪心算法
贪心选择的关键是找到一个最大后是不是能够卖掉stock,重新开始寻找买入机会。比如序列1 3 2 8,如果发现2小于3就完成交易买1卖3,此时由于fee=2,(3-1-fee)+(8-2-fee)<(8-1-fee),所以说明卖早了,令max是当前最大price,当(max-price[i]>=fee)时可以在max处卖出,且不会存在卖早的情况,再从i开始重新寻找买入机会。c++代码如下:
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int profit=0;
int curProfit=0;
int minP=prices[0];
int maxP=prices[0];
int i;
for(i=1;i<prices.size();i++){
minP=min(minP,prices[i]);
maxP=max(maxP,prices[i]);
curProfit=max(curProfit,prices[i]-minP-fee);
if((maxP-prices[i])>=fee){//can just sell the stock at maxP day.
profit+=curProfit;
curProfit=0;
minP=prices[i];
maxP=prices[i];
}
}
return profit+curProfit;//the last trade have to be made if there is some profit
}
};
curProfit记录了当前一次交易能得到的最大收益,只有当maxP-prices[i]>=fee时,才将curProfit累加到总的收益中。最后一次交易不需要考虑是否早卖了,所以直接累加最后一次的curProfit。
---------------------
作者:Zarlove
来源:CSDN
原文:https://blog.csdn.net/zarlove/article/details/78323469
版权声明:本文为博主原创文章,转载请附上博文链接!
No comments:
Post a Comment