九章演算法 | Facebook 面試題 : 有手續費的買賣股票問題

撰文 | JZ

專欄 | 九章演算法

題目描述

1. 給定一支股票每天的價格以及進行一次賣出所需要的交易費，每次最多只能擁有 一支股票，問能獲得的最大利潤是多少。

2. 輸入輸出

ⅰ. Input: prices = [1, 3, 2, 8, 4, 9], fee = 2

ⅱ. Output: 8.

解題思路分析

1. 我們考慮最樸素的方法，對於每一天，如果當前有股票，考慮出售或者保留，如果沒股票，考慮購買或者跳過，進行dfs搜索。每天都有兩種操作，時間複雜度為O(2^n)

2. 如何優化呢？我們用動態規劃的思想來解決這個問題，考慮每一天同時維護兩種狀態：擁有股票(own)狀態和已經售出股票(sell)狀態。用own和sell分別保留這兩種狀態到目前為止所擁有的最大利潤。 對於sell，用前一天own狀態轉移，比較賣出持有股是否能得到更多的利潤，即sell = max(sell , own + price - fee)， 而對於own , 我們考慮是否買新的股票更能賺錢(換言之，更優惠），own=max( own, sell-price)

3. 初始化我們要把sell設為0表示最初是sell狀態且沒有profit，把own設為負無窮因為最初不存在該狀態，我們不希望從這個狀態進行轉移

4. 因為我們保存的都是最優狀態，所以在買賣股票時候取max能保證最優性不變

5. 最後直接返回sell即可

參考程序

http://www.jiuzhang.com/solution/best-time-to-buy-and-sell-stock-with-transaction-fee/

面試官角度分析

本題是一道中等偏簡單難度的題目，需要用到動態規劃的思想，利用以前的狀態去更新當前狀態，給出正確的O（n）解法可以達到hire要求

lintcode相關問題

http://lintcode.com/en/problem/best-time-to-buy-and-sell-stock/

推薦閱讀：