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

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

LeetCode - 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.

针对一个方法团灭 6 道股票问题 - 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）这个解题框架，进行小试牛刀。

参考资料

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</li>. Selling at prices[3] = 8</li>. Buying at prices[4] = 4</li>. Selling at prices[5] = 9</li>The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note: . 0 < prices.length ⇐ 50000.</li> . 0 < prices[i] < 50000.</li> . 0 ⇐ fee < 50000.</li>

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * Runtime: 3 ms, faster than 100.00% of Java online submissions for Best Time to Buy and Sell Stock with Transaction Fee.
 * Memory Usage: 54.3 MB, less than 27.27% of Java online submissions for Best Time to Buy and Sell Stock with Transaction Fee.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-28 19:48
 */
public int maxProfit(int[] prices, int fee) {
    int dp0 = 0;
    int dp1 = Integer.MIN_VALUE;
    for (int i = 0; i < prices.length; i++) {
        dp0 = Math.max(dp0, dp1 + prices[i]);
        dp1 = Math.max(dp1, dp0 - prices[i] - fee);
    }
    return dp0;
}