Best Time To Buy And Sell Stock 買(mǎi)賣(mài)股票最佳時(shí)機(jī)

elliott_hu 發(fā)布于2019-08-15 15:40 / 1857人閱讀

摘要：關(guān)鍵字，，算法，，動(dòng)態(tài)規(guī)劃，上關(guān)于主題的題目有四個(gè)這四個(gè)題目難度依次遞增。其中第四個(gè)問(wèn)題是尋求一個(gè)通解，在給定和最大買(mǎi)賣(mài)次數(shù)的情況下，求最大收益。首先大致的解題方向是動(dòng)態(tài)規(guī)劃，這個(gè)應(yīng)該不難想到。之后就是怎么找到狀態(tài)，怎么列狀態(tài)轉(zhuǎn)移方程。

關(guān)鍵字：leetcode，Best Time To Buy And Sell Stock，算法，algorithm，動(dòng)態(tài)規(guī)劃，dynamic programming

leetcode 上關(guān)于Best Time to Buy and Sell Stock主題的題目有四個(gè)：

https://leetcode.com/problems...

這四個(gè)題目難度依次遞增。大致意思就是，給我們一個(gè) List prices ，然后讓我們找到怎么買(mǎi)賣(mài)才能獲得最大收益。其中第四個(gè)問(wèn)題是尋求一個(gè)通解，在給定 prices和最大買(mǎi)賣(mài)次數(shù)k的情況下，求最大收益。

首先大致的解題方向是動(dòng)態(tài)規(guī)劃，這個(gè)應(yīng)該不難想到。之后就是怎么找到狀態(tài)，怎么列狀態(tài)轉(zhuǎn)移方程。考慮某一天的情況，可以有如下三種狀態(tài)：

當(dāng)天買(mǎi)入

當(dāng)天賣(mài)出

當(dāng)天什么也沒(méi)做

因?yàn)檫@個(gè)題目我們要找到最大收益，所以，如果最后一天的狀態(tài)是買(mǎi)入的話，那么其收益一定不是最大的，因?yàn)樽詈笠惶熨I(mǎi)入的話，就沒(méi)有機(jī)會(huì)賣(mài)出了。那么，上面的三個(gè)狀態(tài)可以減少到兩個(gè)：

當(dāng)天賣(mài)出。

賣(mài)出，但是不在當(dāng)天（即在前面的某一天）。

所以，我們用 soldAtToday[k] 來(lái)表示當(dāng)天賣(mài)出且賣(mài)出的時(shí)候交易了 k 手的時(shí)候的最大收益，soldNotAtToday[k] 代表在之前某天賣(mài)出，且當(dāng)前交易手?jǐn)?shù)為 k 的時(shí)候的最大收益。那么，狀態(tài)轉(zhuǎn)移方程就可以用如下偽代碼描述：

soldAtToday[k] =  max(soldAtYesterday[k] + price, soldNotAtYesterday[k - 1] + price);
soldNotAtToday[k] = max(soldAtYesterday[k], soldNotAtYesterday[k]);

其中，k 是交易次數(shù)。需要注意的是soldAtToday[k] = max(soldAtYesterday[k] + price, soldNotAtYesterday[k - 1] + price);中第一個(gè)備選項(xiàng)是soldAtYesterday[k]，而不是soldAtYesterday[k - 1]，其含義就是，把本應(yīng)該昨天賣(mài)的延長(zhǎng)一天到今天賣(mài)，所以交易次數(shù)還是 k 。

具體實(shí)現(xiàn)的時(shí)候，我們發(fā)現(xiàn) soldAtToday 和 soldNotAtToday 都是只依賴(lài)于 soldAtYesterday 和 soldNotAtYesterday，所以我們可以利用兩個(gè)長(zhǎng)度為 k + 1 的數(shù)組來(lái)完成 today 和 yesterday 數(shù)據(jù)的存儲(chǔ)。

package BestTimeToBuyAndSellStock.VersionIV;

@SuppressWarnings("Duplicates")
class Solution {

    private int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++) {
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        }
        return profit;
    }

    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length <= 1 || k <= 0) {
            return 0;
        }

        int len = prices.length;

        if (k >= len / 2) return quickSolve(prices);


        int today = 1;
        int yesterday = 0;
        int[][] soldAt = new int[2][k + 1];
        int[][] soldNotAt = new int[2][k + 1];

        soldAt[today][0] = 0;
        soldAt[yesterday][0] = 0;
        soldNotAt[today][0] = 0;
        soldNotAt[yesterday][0] = 0;

        for (int i = 0; i < k + 1; i++) {
            soldAt[yesterday][i] = 0;
            soldNotAt[yesterday][i] = 0;
        }

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i] - prices[i - 1];
            for (int j = 1; j < k + 1; j++) {
                soldAt[today][j] = Math.max(
                        soldAt[yesterday][j] + price,
                        soldNotAt[yesterday][j - 1] + price
                );
                soldNotAt[today][j] = Math.max(
                        soldAt[yesterday][j],
                        soldNotAt[yesterday][j]
                );
            }
            int tmp = yesterday;
            yesterday = today;
            today = tmp;
        }

        return Math.max(soldAt[yesterday][k], soldNotAt[yesterday][k]);
    }
}

觀察代碼發(fā)現(xiàn)，開(kāi)頭多了一個(gè) quickSolve 。這是因?yàn)椋绻苯影焉厦嫖覀兠枋龅乃惴▽?shí)現(xiàn)出來(lái)，提交上去，會(huì)出現(xiàn) TimeLimted 的問(wèn)題。仔細(xì)分析了一下超時(shí)的用例，發(fā)現(xiàn)他們的特征是 k 很大。其實(shí)，當(dāng) k 大于 prices.length / 2 的時(shí)候，就相當(dāng)于沒(méi)有 k 的限制，即隨便買(mǎi)賣(mài)了，因?yàn)椴豢紤]當(dāng)天買(mǎi)當(dāng)天賣(mài)的情況，或者把當(dāng)天買(mǎi)賣(mài)的收益虛擬的記為 0 。那么我們的算法就退化成最簡(jiǎn)單的情況，于是使用一個(gè) quickSolve 來(lái)解決即可。
這個(gè)題目也對(duì)我們?nèi)粘９ぷ魈峁┝藛⑹荆撼霈F(xiàn)問(wèn)題了，找到瓶頸，分析特征，然后突破。