Youraregivenanarrayofintegersprices,forwhichthei-thelementisthepriceofagivenstockondayi;andanon-negativeintegerfeerepresentingatransactionfee.
Youmaycompleteasmanytransactionsasyoulike,butyouneedtopaythetransactionfeeforeachtransaction.Youmaynotbuymorethan1shareofastockatatime(ie.youmustsellthestocksharebeforeyoubuyagain.)
Returnthemaximumprofityoucanmake.
Example1:
Input:prices=[1,3,2,8,4,9],fee=2Output:8Explanation:Themaximumprofitcanbeachievedby:Buyingatprices[0]=1Sellingatprices[3]=8Buyingatprices[4]=4Sellingatprices[5]=9Thetotalprofitis((8-1)-2)+((9-4)-2)=8.
Note:0<prices.length<=50000.0<prices[i]<50000.0<=fee<50000.
给定一个数组，数组中的第i个元素为一只股票第i天的价格。现在求买卖股票所能得到的最大值。如果用贪心的思想去解这道题，应注意贪心选择与产生的子问题无关。因此，只能确定应该在何时买入，而无法确定何时卖出(因为没有标准去衡量赚多少钱是最优的)。所以，我们需要制定一个判断标准去衡量应该在何时买入。如果对于一个单调上升的数列，其最优解必然是最大值-最小值。但如果指定的区间内不是单调上升的，那么假定存在一个比区间最小值大的某个值，和比区间最大值小的某个值，能将这个区间分成两部分，并且使这两部分的各自的最大值-最小值的和大于原区间最大值-最小值。这样，从左侧开始遍历数组，按照选择买入的判断标准，不断将原有区间细分，最终求得最优解
classSolution{public:intmaxProfit(vector<int>&prices,intfee){intlen=prices.size();if(len==0||len==1)return0;intsum=0;intpeak=0;intleast=INT_MAX;for(autoele:prices){if(peak-ele>fee){sum+=(peak-least-fee);least=ele;peak=0;}least=min(ele,least);if(ele-least>fee){peak=max(peak,ele);}}if(peak-least>fee)sum+=(peak-least-fee);returnsum;}};
注意：
由于是判断何时买入，所以在执行买入前先执行卖出操作卖出操作时注意对下个区间最大值和最小值的初始化由于判断何时买入，在没有新的买入前不进行卖出，因此在循环结束时，要进行最后一次卖出
