Leetcode188. Best Time to Buy and Sell Stock IV

pingink 發(fā)布于2019-08-15 14:20 / 2911人閱讀

摘要：題目要求有一個整數(shù)數(shù)組，每一位上的值代表那一天的股票價格。現(xiàn)在假設最多能夠進行次交易，問最大的收入是多少思路和代碼這里采用了動態(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 the maximum profit. You may complete at most k transactions.

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

有一個整數(shù)數(shù)組，每一位上的值代表那一天的股票價格。現(xiàn)在假設最多能夠進行k次交易，問最大的收入是多少？

思路和代碼

這里采用了動態(tài)編程的思想。假設我們希望得到第j天最多進行i次交易的最大利潤，我們首先想到的是，可以通過比較第j-1天最多進行i次交易的利潤，以及第j-1天進行i-1次交易然后最后一次交易為賣出當天的股票所帶來的利潤。

但是這里存在一個問題，也就是說，如果第j-1天進行的第i-1次交易剛好為賣出第j-1天的股票，而我們不能在這個數(shù)據(jù)上直接加上在第j天出售股票所獲得的利潤，因為我們在j-1天根本就沒有購入股票！所以我們需要在j-1天進行i-1次交易獲得最大利潤的基礎上減去第j天的股票代表我們買入了第j天的股票，從而用于下一輪的計算。

public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (k >= len / 2) return quickSolve(prices);
        
        int[][] t = new int[k + 1][len];
        for (int i = 1; i <= k; i++) {
            int tmpMax =  -prices[0];
            for (int j = 1; j < len; j++) {
                t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
                tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
            }
        }
        return t[k][len - 1];
    }
    

    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;
    }

想要了解更多開發(fā)技術，面試教程以及互聯(lián)網(wǎng)公司內推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

GPU云服務器云服務器 redis Time to live Buy Sell Stock

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68551.html

[Leetcode] Best Time to Buy and Sell Stock 買賣股票的最佳

摘要：雙指針法復雜度時間空間思路根據(jù)買賣股票的特性，我們必須先低價買，再高價賣，這個找最大收益的過程實際上是找到目前為之的最低價。我們可以利用這個之前計算的結果降低時間復雜度不過代價是額外空間，所以需要把到的最大收益存在數(shù)組中。 Best Time to Buy and Sell Stock I Say you have an array for which the ith element...

nanchen2251 2019-08-14 16:11 評論0 收藏0
[LeetCode]Best Time to Buy and Sell Stock with Coo

摘要：分析因為當前日期買賣股票會受到之前日期買賣股票行為的影響，首先考慮到用解決。所以我們可以用兩個數(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 ...

xcc3641 2019-08-14 15:08 評論0 收藏0
LeetCode 309. Best Time to Buy and Sell Stock with

摘要：示例輸入輸出解釋對應的交易狀態(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. ...

劉明 2019-07-31 10:04 評論0 收藏0
Best Time To Buy And Sell Stock 買賣股票最佳時機

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

elliott_hu 2019-08-15 15:40 評論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 2019-08-15 13:39 評論0 收藏0