亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[LeetCode]Best Time to Buy and Sell Stock with Coo

xcc3641 / 829人閱讀

摘要：分析因為當前日期買賣股票會受到之前日期買賣股票行為的影響，首先考慮到用解決。所以我們可以用兩個數(shù)組分別記錄當前持股跟未持股的狀態(tài)。

Best Time to Buy and Sell Stock with Cooldown 
Say you have an array for which the ith element is the price of a given stock on day i.


Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:



You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)



Example:


prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
分析

因為當前日期買賣股票會受到之前日期買賣股票行為的影響，首先考慮到用DP解決。

這道題比較麻煩的是有個cooldown的限制，其實本質(zhì)也就是買與賣之間的限制。對于某一天，股票有三種狀態(tài): buy, sell, cooldown, sell與cooldown我們可以合并成一種狀態(tài)，因為手里最終都沒股票，最終需要的結(jié)果是sell，即手里股票賣了獲得最大利潤。所以我們可以用兩個DP數(shù)組分別記錄當前持股跟未持股的狀態(tài)。然后根據(jù)題目中的限制條件，理清兩個DP數(shù)組的表達式。

對于當天最終未持股的狀態(tài)，最終最大利潤有兩種可能，一是今天沒動作跟昨天未持股狀態(tài)一樣，二是昨天持股了，今天賣了。所以我們只要取這兩者之間最大值即可，表達式如下：

sellDp[i] = Math.max(sellDp[i - 1], buyDp[i - 1] + prices[i]);

對于當天最終持股的狀態(tài)，最終最大利潤有兩種可能，一是今天沒動作跟昨天持股狀態(tài)一樣，二是前天還沒持股，今天買了股票，這里是因為cooldown的原因，所以今天買股要追溯到前天的狀態(tài)。我們只要取這兩者之間最大值即可，表達式如下：

buyDp[i] = Math.max(buyDp[i - 1], sellDp[i - 2] - prices[i]);

最終我們要求的結(jié)果是

sellDp[n - 1] 表示最后一天結(jié)束時手里沒股票時的累積最大利潤

當然，這里空間復(fù)雜度是可以降到O(1)的，具體見第二種代碼實現(xiàn)。

復(fù)雜度

time: O(n), space: O(n)

代碼 
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        // 表示當天最終未持股的情況下，當天結(jié)束后的累計最大利潤
        int[] sellDp = new int[prices.length];
        // 表示當天最終持股的情況下，當天結(jié)束后的累計最大利潤
        int[] buyDp = new int[prices.length];
        
        // 考慮初始情況
        buyDp[0] = -prices[0];
        sellDp[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            sellDp[i] = Math.max(sellDp[i - 1], buyDp[i - 1] + prices[i]);
            if (i >= 2) {
                buyDp[i] = Math.max(buyDp[i - 1], sellDp[i - 2] - prices[i]);
            } else {
                buyDp[i] = Math.max(buyDp[i - 1], -prices[i]);
            }
        }
        return sellDp[prices.length - 1];
    }
}
代碼(O(1) space) 
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
    
        int currBuy = -prices[0];
        int currSell = 0;
        int prevSell = 0;
        for (int i = 1; i < prices.length; i++) {
            int temp = currSell;
            currSell = Math.max(currSell, currBuy + prices[i]);
            if (i >= 2) {
                currBuy = Math.max(currBuy, prevSell - prices[i]);
            } else {
                currBuy = Math.max(currBuy, -prices[i]);
            }
            prevSell = temp;
        }
        return currSell;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/65329.html

相關(guān)文章

  • LeetCode 309. Best Time to Buy and Sell Stock with

    摘要：示例輸入輸出解釋對應(yīng)的交易狀態(tài)為買入賣出冷凍期買入賣出思路這道題使用動態(tài)規(guī)劃。狀態(tài)表示當天休息能夠獲得的最大價值，表示當天持有股票能夠獲得的最大價值，表示當天持有股票能夠獲得的最大價值。 Description Say you have an array for which the ith element is the price of a given stock on day i. ...

    劉明 評論0 收藏0

  • 309. Best Time to Buy and Sell Stock with Cooldown

    摘要：題目鏈接來解，要用兩個分別表示現(xiàn)在的操作是還是，優(yōu)化空間用滾動數(shù)組，或者幾個 309. Best Time to Buy and Sell Stock with Cooldown 題目鏈接：https://leetcode.com/problems... dp來解，要用兩個dp array分別表示現(xiàn)在的操作是buy還是sell，優(yōu)化空間用滾動數(shù)組，或者幾個int public clas...

    sorra 評論0 收藏0

  • Best Time To Buy And Sell Stock 買賣股票最佳時機

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

    elliott_hu 評論0 收藏0

  • leetcode 121 Best Time to Buy and Sell Stock

    摘要：求可能的最大利潤題目給了兩個例子最大利潤就是進價為，賣價為的時候，利潤為在這個案例中，進價一直高于售價，所以無法成交，返回。主要注意一下，先買入才能賣出賣價一定要比買入價格高才能成交就可以了。 題目詳情 Say you have an array for which the ith element is the price of a given stock on day i.If yo...

    QLQ 評論0 收藏0

  • Leetcode188. Best Time to Buy and Sell Stock IV

    摘要：題目要求有一個整數(shù)數(shù)組，每一位上的值代表那一天的股票價格?，F(xiàn)在假設(shè)最多能夠進行次交易，問最大的收入是多少思路和代碼這里采用了動態(tài)編程的思想。 題目要求 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find t...

    pingink 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<