leetcode(6)

leetcode(6)

714. Best Time to Buy and Sell Stock with Transaction Fee

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.

class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int s0=0,s1=INT_MIN;
int temp=0;
for(int p : prices)
{
temp=s0;
s0=max(s0,s1+p);
s1=max(s1,temp-p-fee);
}
return s0;
}
};

拿例子 1  3 2 8 4 9来解析下:

在买卖过程中,主要存在两个状态,一个状态时手上有股票的状态S1,另一种状态是手上没有股票的状态S0。p指向当前股价,temp用来记录上次手上没有股票的状态

1 | 3 | 2 8 4 9    光标聚集在位置1,光标之前S0=0,S1=-3 。在此基础上,当光标来到位置1时要么有股票在手 S1=max(S1,temp-p-fee):选择上次有股票状态和上次无股票状态买上这次股票的最大收益额作为该光标处到目前位置的手上有股票的收益额,要么没有股票在手S0=max(S0,S1+p):选择上次无股票状态和上次有股票状态卖掉股票后的最大收益额作为该光标处到目前位置的手上无股票的收益额。这两种情况我们都选最优的情况,不断迭代出最优。

 




So BadJust So SoGoodCoolPretty Cool (还没人评过分呢!)
Loading...

发表评论

电子邮件地址不会被公开。 必填项已用*标注