测试人社区

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

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

Medium

126838Add to ListShare

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 .

思路

有两个变量:

  • crash记录,手上没有股票的最大收益
  • hold记录,手上持有股票的最大收益

每次遇到新的股票,都会更新crash和hold

  • cash = Math.max(cash, hold + prices[i] - fee),以前手上没有股票的收益高,还是当前卖掉股票的收益高
  • hold = Math.max(hold, cash - prices[i]),以前手上持有股票的收益高,还是现在买进股票的收益高

java

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(cash, hold + prices[i] - fee);
            hold = Math.max(hold, cash - prices[i]);
        }
        return cash;
    }
}

python

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        crash, hold = 0, -prices[0]
        for i in range(1, len(prices)):
            crash = max(crash, hold + prices[i] - fee)
            hold = max(hold, crash - prices[i])
        return crash
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """