Leetcode188. Best Time to Buy and Sell Stock IV

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

摘要：題目要求有一個(gè)整數(shù)數(shù)組，每一位上的值代表那一天的股票價(jià)格?，F(xiàn)在假設(shè)最多能夠進(jìn)行次交易，問(wèn)最大的收入是多少思路和代碼這里采用了動(dòng)態(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).

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

思路和代碼

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

但是這里存在一個(gè)問(wèn)題，也就是說(shuō)，如果第j-1天進(jìn)行的第i-1次交易剛好為賣(mài)出第j-1天的股票，而我們不能在這個(gè)數(shù)據(jù)上直接加上在第j天出售股票所獲得的利潤(rùn)，因?yàn)槲覀冊(cè)趈-1天根本就沒(méi)有購(gòu)入股票！所以我們需要在j-1天進(jìn)行i-1次交易獲得最大利潤(rùn)的基礎(chǔ)上減去第j天的股票代表我們買(mǎi)入了第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;
    }

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