Re: [閒聊] 每日LeetCode已回收
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
714. Best Time to Buy and Sell Stock with Transaction Fee
給你一個陣列 prices 表示股票每天的價錢，一個 fee 表示每次賣掉股票的手續費
，一天只能持有一個股票而且進行一次買或賣，求股票的最大收益。
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.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
思路：
1.用DP來動態的紀錄買賣狀態轉移，buy = 當天持有股票, sell = 當天不持有股票
2.當天持有股票只可能是：
一、前一天持有股票，今天不買賣
二、前一天不持有股票，今天買入
當天不持有股票只可能是：
一、前一天不持有股票，今天不買賣
二、前一天持有股票，今天賣掉
狀態轉移方程：
buy[i] = Max(buy[i-1], sell[i-1] - prices[i])
sell[i] = Max(sell[i-1], buy[i-1] + prices[i] - fee)
(賣的當下要多扣手續費)
3.最後取第 n 天的sell即可，最後一天不持有股票一定是最佳收益。
Java Code：
-------------------------------------
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[] buy = new int[n];
int[] sell = new int[n];
buy[0] = -prices[0];
for (int i = 1; i < n; i++) {
buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee);
}
return sell[n - 1];
}
}
-------------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1687403016.A.579.html
討論串 (同標題文章)
完整討論串 (本文為第 353 之 719 篇)：