算法分析股票类型的相关题型
最近在看算法時看到股票類的題目覺得很有意思，在這里對于比較好的方法做一下總結，盡量讓大家看一遍就可以記住這個問題該怎么解決。其實學習算法是一個痛苦的過程，但不管怎樣最終提升的是自己的能力，所以希望讀到文章的小伙伴如果也是同樣對算法感興趣或者沒有興趣但想學習算法的同學，努力堅持，在某一天你就會突然發現，我怎么這么牛哈哈！
不扯閑話了。最近看到有股票相關的算法題目，于是把相關類型的題目做了總結記錄在這里，大家在看到一個問題的同時也可以看一下其他的類型的題目。大家可以先不要看后面的解析自己做一下，我在這里的解法也只是給大家提供一個解題的思路和方法，如果大家有更好的解體思路和方式，可以留言，我們大家一起探討。
對于股票類型的題目，都是求如何獲取最大的利益，大致整理如下：
可能有的同學對于股票買賣不是很清楚，我在這里大致說一下，一只股票在每一天的價格可能都不一樣，你需要選擇低價的時候買入，高價的時候賣出才能盡可能獲得較高的利益，題目中還有一個要求就是你在買入以后只有賣出之后才能繼續進行買賣。例如某個股票五天的價格分別為7,1,5,3,6,4，在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5，同時，你不能在買入前賣出股票。其他不懂得地方大家可以自行百度。接下來我們由簡單到復雜來分析一下。
這里我們給定一個整數數組 prices，其中第 i 個元素代表了第 i 天的股票價格。
買賣股票的最佳時機-最多只允許完成一筆交易（即買入和賣出一支股票一次）
我們先來看最多只允許完成一筆交易的情況。我們來假設自己來購買股票。隨著時間的推移，每天我們都可以選擇出售股票與否。那么，假設在第 i 天，如果我們要在今天賣股票，那么我們能賺多少錢呢？顯然，如果我們真的在買賣股票，我們肯定會想：如果我是在歷史最低點買的股票就好了。這里采用動態規劃的思想進行解決。通常采用動態規劃解決問題主要步驟分為三步：
1.定義狀態 2.找出狀態轉移方程 3.初始狀態確定那么這里的這三個步驟分別應該怎么定義呢？我們假設動態規劃表為dp[i],表示以 prices[i]為結尾的子數組的最大利潤，這就定義好了狀態；假如計劃在第 i 天賣出股票，那么第i日最大利潤dp[i] 應該等于前 i - 1 日最大利潤 dp[i-1] 和第 i日賣出的最大利潤中的最大值，用數學公式表示即：
dp[i]=max(dp[i?1],prices[i]?min(prices[0:i]))以上就是狀態轉移的方程；
接下來需要定義初始狀態dp[0],即首日的收益，顯然dp[0]=0，依據以上公式遍歷，最后得到的dp[n-1]即為最后的最大利益，其中n為dp列表的長度。
下面是代碼：
由于 dp[i] 只與 dp[i - 1] , prices[i] , minPrice相關，因此可使用一個變量profit代替 dp列表。優化后的轉移方程為：
profit=max(profit,prices[i]?min(minPrice,prices[i])則代碼可以優化為：
// 最多只允許完成一筆交易 /*** @Author likangmin* @create 2020/10/27 19:27*/public static int maxProfit(int[] prices) {int minprice=Integer.MAX_VALUE,profit=0;for(int price:prices){minprice=Math.min(minprice,price);profit=Math.max(profit,price-minprice);}return profit;}看起來更加簡潔，這就解決了最多只允許完成一筆交易的情況。大家對于這類問題有沒有了初步的一個解題思路了呢？相信對這個有了一定的了解之后對于后面的幾類問題會相對比較容易理解一些。
買賣股票的最佳時機-盡可能地完成更多的交易（多次買賣一支股票）
接下來看一個比較簡單的問題:盡可能地完成更多的交易（多次買賣一支股票）。為什么說簡單呢？其實只要把題目的意思翻譯成大家都通俗易懂的意思，那就會恍然大悟。大家看完以下的解釋就會知道，同樣你也會覺得非常簡單。對于多次買賣沒有限定次數的情況，在這里給大家分為三個場景:
單獨交易日:假設今天的價格是p1,明天的價格是p2，則今天買入明天賣出可以賺取的利益為p2-p1（負值代表虧損） 連續上漲交易日：設此上漲交易日股票價格分別為p1,p2......pn，則第一天買最后一天賣最大為pn-p1，很多同學可能就是在這里不知道則呢忙處理，其實這個可以等價成每天都買賣，即pn-p1=(p2-p1)+(p3-p2)+......+(pn-pn-1)。 連續下降交易日：不進行買賣的話收益最大。則依據以上分析，我們可以按照下main的操作進行獲取不限次數交易的最大利益：遍歷整個股票交易日價格列表，所有上漲交易日都買賣（賺到所有利潤），所有下降交易日都不買賣（永不虧錢），具體定義流程如下：
1.設 res為第 i-1 日買入與第 i 日賣出賺取的利潤，即 res= prices[i] - prices[i - 1] ； 2.當該天利潤為正 res> 0，則將利潤加入總利潤 profit；當利潤為 0 或為負，則直接跳過； 3.遍歷完成后，返回總利潤 profit即為最大的利潤以下是代碼：
// 多次買賣 /*** @Author likangmin* @create 2020/10/27 20:00*/ public int maxProfit(int[] prices) {int profit=0;for(int i=1;i<prices.length;i++){int res=prices[i]-prices[i-1];if(res>0){profit+=res;}}return profit;}是不是很簡單？其實只要你理解了題目的真正意思，那基本都可以按照思路自己寫出來。
買賣股票的最佳時機-最多可以完成 兩筆 交易
接下里讓我們看最多交易兩次的問題。
在一定的天數內，我們最多可以進行兩次交易，分為 買-賣-買-賣，所以問題的關鍵就是找到這4個點的最優分布。而第一次買入 / 第一次賣出 / 第二次買入 / 第二次賣出 這四個過程都可能發生在今天。為了更好的說明，在這里我們舉一個例子：
基于以上的一個狀態，定義了4個變量與上述4個過程對應：
第一次買入后的狀態： minPrice1: 第一次買入后的利潤 第一次賣出后的狀態： maxProfit1: 第一次賣出后的利潤 第二次買入后的狀態： maxProfitAtferBuy第二次買入后的利潤 第二次賣出后的狀態： maxProfit2:第二次賣出后的利潤然后遍歷每一天，在每一天我們都作 4個假設，并更新上面4個狀態：
假設今天第一次買入：更新 最低價格 假設今天第一次賣出：更新 第一次最大利潤 假設今天第二次買入：更新 第二次買后的最大剩余利潤 假設今天第二次賣出：更新 當天能獲得的最大利潤有了以上的一個分析，那就很容易的將代碼寫出來了：
// 最多交易兩次 /*** @Author likangmin* @create 2020/10/27 20:10*/ public static int maxProfit2(int[] prices) {int minPrice1 = Integer.MAX_VALUE;int maxProfit1 = 0;int maxProfitAfterBuy = Integer.MIN_VALUE;int maxProfit2 = 0;for(int price : prices) {// 1.第一次最小購買價格minPrice1 = Math.min(minPrice1, price);// 2.第一次賣出的最大利潤maxProfit1 = Math.max(maxProfit1, price - minPrice1);// 3.第二次購買后的剩余凈利潤maxProfitAfterBuy = Math.max(maxProfitAfterBuy, maxProfit1 - price );// 4.第二次賣出后，總共獲得的最大利潤（第3步的凈利潤 + 第4步賣出的股票錢）maxProfit2 = Math.max(maxProfit2, price + maxProfitAfterBuy);}return maxProfit2;}買賣股票的最佳時機-最多可以完成 k 筆交易
接下來看交易K次的問題，這個題和兩次交易 基本就可以歸為一個類型。我們在沒進行交易的時候，利潤是為 0 的；每次買入，手上的錢會減少，即：利潤減少 --；每次賣出，手上的前會增多，即：利潤增加 ++。每次的買入狀態跟上次的賣出狀態相關，每次的賣出狀態跟上次的買入狀態相關。有的同學可能不太理解，這里做一下簡單的例子介紹：
第 1 次買入的時候，上次的狀態： 利潤為 0 的時候 第 1 次賣出的時候，上次的狀態：第 1 次買入 第 3 次買入的時候，上次的狀態：第 2 次賣出 ...當然狀態都是指操作完成后的利潤。這樣的我們就很自然地會想到動態規劃表來記錄這樣一個狀態變化的過程;我們在每一天都把這 k 次交易都模擬一遍，記錄這一天的 k 次交易的狀態，并在后續不停的更新。所以先要定義好各個步驟需要的信息：
狀態定義：dp[i][j]表示第 i次交易, 行為是「買 | 賣」的狀態，其中 j=0 表示買；j = 1 表示賣 狀態轉移： 第 i 次交易的買入： dp[i][0] = dp[i - 1][1] - price 第 i 次交易的賣出： dp[i][1] = dp[i][0] + price 其中 priceprice 表示當天的價格 初始化：dp[i][0]=?∞ (方便比較)我們需要注意的是，一次交易比較特殊，單獨計算一下 dp[0][0] 和dp[0][1],后面 k-1k?1 次都是基于第一次交易，另外交易數 k>length/2 的時候，k 就沒有意義了，因為天數限制了交易次數必須小于 length/2，所以這種情況也就相當于無限次交易。有了上面的分析，接下來我們就很自然的寫出代碼：
// 交易K次 /*** @Author likangmin* @create 2020/10/27 20:20*/ public int maxProfit(int k, int[] prices) {if (k < 1 ) { return 0; }// k 超過了上限，也就變成了 無限次交易問題if (k > prices.length / 2) {return 不限交易次數(prices);}// 狀態定義int [][] dp = new int[k][2];// 初始化for (int i = 0; i < k; i++) {dp[i][0] = Integer.MIN_VALUE;}// 遍歷每一天，模擬 k 次交易，計算并更新狀態for (int p : prices) {dp[0][0] = Math.max(dp[0][0], 0 - p); // 第 1 次買dp[0][1] = Math.max(dp[0][1], dp[0][0] + p); // 第 1 次賣for (int i = 1; i < k; i++) {dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] - p); // 第 i 次買dp[i][1] = Math.max(dp[i][1], dp[i][0] + p); // 第 i 次賣}}return dp[k - 1][1];}買賣股票的最佳時機-可以無限次地完成交易，但是你每筆交易都需要付手續費
接下來分析不限交易次數但是卻會收取手續費的問題。當我們不持有股票時假設最大利潤為profit1，當我們持有股票時的最大利潤profit2,則在第 i 天時，我們需要根據第 i - 1天的狀態來更新 profit1 和 profit2 的值。對于profit1，我們可以保持不變，或者將手上的股票賣出，狀態轉移方程為：
profit1 = max(profit1 , profit2 + prices[i] - fee)對于 profit2，我們可以保持不變，或者買入這一天的股票，狀態轉移方程為：
profit2 = max(profit2 , cash - prices[i]) // 不限次數但收取手續費 /*** @Author likangmin* @create 2020/10/27 20:30*/ public int maxProfit(int[] prices, int fee) {int profit1 = 0, profit2 = -prices[0];for (int i = 1; i < prices.length; i++) {profit1 = Math.max(profit1, profit2 + prices[i] - fee);profit2 = Math.max(profit2, profit1 - prices[i]);}return profit1;}買賣股票的最佳時機-盡可能地完成更多的交易（多次買賣一支股票），賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)
接下來看最后一個問題：不限交易次數但是有冷凍期。我們用 f[i] 表示第 i 天結束之后的「累計最大收益」。根據題目描述，由于我們最多只能同時買入（持有）一支股票，并且賣出股票后有冷凍期的限制，因此我們會有三種不同的狀態：
我們目前持有一支股票，對應的「累計最大收益」記為f[i][0]； 我們目前不持有任何股票，并且處于冷凍期中，對應的「累計最大收益」記為f[i][1]； 我們目前不持有任何股票，并且不處于冷凍期中，對應的「累計最大收益」記為 f[i][2]。如何進行狀態轉移呢？在第 i 天時，我們可以在不違反規則的前提下進行「買入」或者「賣出」操作，此時第 ii 天的狀態會從第 i-1 天的狀態轉移而來；我們也可以不進行任何操作，此時第 i 天的狀態就等同于第 i-1 天的狀態。那么我們分別對這三種狀態進行分析：
對于f[i][0]，我們目前持有的這一支股票可以是在第i?1 天就已經持有的，對應的狀態為 f[i?1][0]； 或者是第 i 天買入的，那么第i?1 天就不能持有股票并且不處于冷凍期中，對應的狀態為f[i?1][2] 加上買入股票的負收益prices[i]。因此狀態轉移方程為： f[i][0]=max(f[i?1][0],f[i?1][2]?prices[i]) 對于f[i][1]，我們在第 i 天結束之后處于冷凍期的原因是在當天賣出了股票，那么說明在第 i?1 天時我們 必須持有一支股票，對應的狀態為f[i?1][0] 加上賣出股票的正收益prices[i]。因此狀態轉移方程為： f[i][1]=f[i?1][0]+prices[i] 對于 f[i][2]，我們在第 i 天結束之后不持有任何股票并且不處于冷凍期，說明當天沒有進行任何操作， 即第 i?1 天時不持有任何股票：如果處于冷凍期，對應的狀態為 f[i?1][1]；如果不處于冷凍期，對應的狀態為 f[i?1][2]。 因此狀態轉移方程為： f[i][2]=max(f[i?1][1],f[i?1][2])這樣我們就得到了所有的狀態轉移方程。如果一共有 n 天，那么最終的答案即為：
max(f[n?1][0],f[n?1][1],f[n?1][2])注意到如果在最后一天（第 n-1n?1 天）結束之后，手上仍然持有股票，那么顯然是沒有任何意義的。因此更加精確地，最終的答案實際上是f[n?1][1] 和 f[n?1][2] 中的較大值，即：
max(f[n?1][1],f[n?1][2])初始值應該怎么定義呢？在第 0 天時，如果持有股票，那么只能是在第 0 天買入的，對應負收益 ?prices[0]；如果不持有股票，那么收益為零,即：
f[0][0]=?prices[0] f[0][1]=0 f[0][2]=0有了以上條件則可以直接寫出代碼：
// 不限次數但有冷凍期 /*** @Author likangmin* @create 2020/10/27 20:50*/ public int maxProfit4(int[] prices) {if (prices.length == 0) {return 0;}int n = prices.length;// f[i][0]: 手上持有股票的最大收益// f[i][1]: 手上不持有股票，并且處于冷凍期中的累計最大收益// f[i][2]: 手上不持有股票，并且不在冷凍期中的累計最大收益int[][] f = new int[n][3];f[0][0] = -prices[0];for (int i = 1; i < n; ++i) {f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);f[i][1] = f[i - 1][0] + prices[i];f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);}return Math.max(f[n - 1][1], f[n - 1][2]);}關于股票相關類型已分析完了。同學們有沒有豁然開朗的感覺？其實大部分解題的思想都是基于動態規劃，對動態規劃還不是很熟的同學可以自己找資料找資料學習一下。只要搞懂了其中的原理，寫出狀態轉移方程，那么問題基本上就可以迎刃而解了。我這里只是提供一個解體的大概思路，并不代表是最好的解法，如果有更好解法且更讓人一看就懂的大家可以提出來一起學習。
注：如轉載，請注明原始地址。
總結
以上是生活随笔為你收集整理的算法分析股票类型的相关题型的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 修路问题算法的总结
- 下一篇： 解决SQL注入与XSS攻击