Best Time to Buy and Sell Stock III Leetcode Python

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 two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). この問題は2つの方法で解くことができ、1つ目の解法はそれぞれ左から右へ1回走査することと、右から左へ1回走査することで得られた最大のmaxproを配列の中に入れてstack 1 stack 2が最後に解くときにstack 1[i]+stack 2[i+1]を得た最大値が最大値である.コードは次のとおりです.

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        if len(prices)==0:
            return 0
        stack1=[]
        stack2=[]
        lowprice=prices[0]
        maxpro=0
        highprice=prices[-1]
        for index in range(len(prices)):
            lowprice=min(lowprice,prices[index])
            maxpro=max(maxpro,prices[index]-lowprice)
            stack1.append(maxpro)
        maxpro=0
        for index in reversed(range(len(prices))):
            highprice=max(highprice,prices[index])
            maxpro=max(maxpro,highprice-prices[index])
            stack2.insert(0,maxpro)
        
        for index in range(len(prices)-1):
            maxpro=max(maxpro,stack1[index]+stack2[index+1])
        return maxpro
            

2つ目の方法はダイナミックプランニングの方法で解きます
iはi日目jは合計j回の取引が可能であることを示す
グローバル最適式はg[j]=max(g[j],l[j])である.
ローカル最適表現は、現在の最適表現と前のグローバル最適表現に現在稼ぐことができるお金を加えた最大表現です.
l[j]=max(g[j-1]+max(dif,0),l[j]+dif)
具体的なコードは以下の通りです.

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        g=[0,0,0]
        l=[0,0,0]
        for i in range(len(prices)-1):
            dif=prices[i+1]-prices[i]
            for j in reversed(range(1,3)):
                l[j]=max(g[j-1]+max(dif,0),l[j]+dif)
                g[j]=max(l[j],g[j])
        return g[2]