思路概述

I、只許購買一次股票。遍歷所有時(shí)間的股票價(jià)格，以當(dāng)前股票價(jià)格之前出現(xiàn)過的最低價(jià)作為買入價(jià)，并計(jì)算出當(dāng)天價(jià)格出售的收益，與曾經(jīng)的最大收益對比，遍歷完即可的得到最大可能收益；
II、交易次數(shù)不限，但每次只能持有一只股票。就可以用貪心法，只要當(dāng)天價(jià)格高于前一天，就加入到收益之中去；
III、最多兩次購買股票。動(dòng)態(tài)規(guī)劃問題，可以以第i天未分界點(diǎn)，計(jì)算前面的單次股票最大收益和后面股票的最大收益，然后求兩者和的最大值作為最終的收益。
IV、特殊的動(dòng)態(tài)規(guī)劃問題，Local[i][j]表示在到達(dá)第i天時(shí)最多可進(jìn)行j次交易并且最后一次交易在最后一天賣出的最大利潤，此為局部最優(yōu)。Global[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易的最大利潤，此為全局最優(yōu)。特別注意，遞推公式的max函數(shù)實(shí)際上代表了對過去狀態(tài)產(chǎn)生的多個(gè)結(jié)果進(jìn)行擇優(yōu)。

特殊動(dòng)態(tài)規(guī)劃問題公式

Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + difference(狀態(tài)增益值)
Global[i][j] = max(Local[i][j], Global[i-1][j])
理解公式很重要。

I

描述

假設(shè)有一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。如果你最多只允許完成一次交易(例如,一次買賣股票),設(shè)計(jì)一個(gè)算法來找出最大利潤。

樣例

給出一個(gè)數(shù)組樣例 [3,2,3,1,2], 返回 1

代碼

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        maxProfit = 0
        if len(prices) == 0:
            return maxProfit
        minPrice = prices[0]
        for i in range(1, len(prices)):
            minPrice = min(minPrice, prices[i])
            maxProfit = max(maxProfit, prices[i]-minPrice)
        return maxProfit

II

描述

假設(shè)有一個(gè)數(shù)組，它的第i個(gè)元素是一個(gè)給定的股票在第i天的價(jià)格。設(shè)計(jì)一個(gè)算法來找到最大的利潤。你可以完成盡可能多的交易(多次買賣股票)。然而,你不能同時(shí)參與多個(gè)交易(你必須在再次購買前出售股票)。

樣例

給出一個(gè)數(shù)組樣例[2,1,2,0,1], 返回 2

代碼

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        maxProfit = 0
        if len(prices) == 0:
            return maxProfit
        for i in range(1, len(prices)):
            maxProfit = maxProfit + max(0, prices[i]-prices[i-1])
        return maxProfit

III

描述

假設(shè)你有一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。設(shè)計(jì)一個(gè)算法來找到最大的利潤。你最多可以完成兩筆交易。

樣例

給出一個(gè)樣例數(shù)組 [4,4,6,1,1,4,2,5], 返回 6

代碼

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        if len(prices) <= 1:
            return 0
        ProfitLift = [0 for i in range(len(prices))]
        ProfitRight = [0 for i in range(len(prices))]
        minPrice = prices[0]
        for i in range(1, len(ProfitLift)):
            minPrice = min(minPrice, prices[i])
            ProfitLift[i] = max(ProfitLift[i-1], max(ProfitLift[i], prices[i]-minPrice))
        maxPrice = prices[-1]
        for i in reversed(range(1, len(ProfitRight))):
            maxPrice = max(maxPrice, prices[i])
            ProfitRight[i-1] = max(ProfitRight[i], max(ProfitRight[i-1], maxPrice-prices[i-1]))
        result = 0
        for i in range(0, len(prices)):
            result = max(result, ProfitLift[i] + ProfitRight[i])
        return result        

IV

描述

假設(shè)你有一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。
設(shè)計(jì)一個(gè)算法來找到最大的利潤。你最多可以完成 k 筆交易。

樣例

給定價(jià)格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.

挑戰(zhàn)

O(nk) 時(shí)間序列。

代碼

class Solution:
    """
    @param nums: A list of integers
    @param k: An integer denote to find k non-overlapping subarrays
    @return: An integer denote the sum of max k non-overlapping subarrays
    """
    def maxProfit(self, K, prices):
        # write your code here
        if len(prices) <=1:
            return 0
        elif K >= len(prices):
            result = 0
            for i in range(1, len(prices)):
                result = max(prices[i]-prices[i-1], 0) + result
            return result
        else:
            Local = [[0 for i in range(K + 1)] for i in range(len(prices) + 1)]
            Global = [[0 for i in range(K + 1)] for i in range(len(prices) + 1)]
    
            for i in range(1, len(prices)+1):
                for j in range(1, K+1):
                    if j*2 > i:
                        Local[i][j] = 0
                        Global[i][j] = 0
                    else:
                        Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + (prices[i-1] - prices[i-2])
                        Global[i][j] = max(Local[i][j], Global[i-1][j])
            return max(Global[-1])

(優(yōu)化空間使用)

class Solution:
    """
    @param K: An integer
    @param prices: An integer array
    @return: Maximum profit
    """
    def maxProfit(self, K, prices):
        # write your code here
        if len(prices) <=1:
            return 0
        elif K >= len(prices):
            result = 0
            for i in range(1, len(prices)):
                result = max(prices[i]-prices[i-1], 0) + result
            return result
        else:
            Local = [[0 for j in range(K+1)] for i in range(2)]
            Global = [[0 for j in range(K+1)] for i in range(2)]
            
            for i in range(1, len(prices)+1):
                for j in range(1, K+1):
                    if j*2 >i:
                        Local[1][j] = 0
                        Global[1][j] = 0
                    else:
                        Local[1][j] = max(Local[0][j], Global[0][j-1]) + (prices[i-1] - prices[i-2])
                        Global[1][j] = max(Local[1][j], Global[0][j])
                for j in range(1, K+1):
                    Local[0][j] = Local[1][j]
                    Global[0][j] = Global[1][j]
            return max(Global[0])

題目來源

https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-i/description
https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-ii/description
https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iii/description
https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv/description