LeetCodeが株を売買する最適な時間シリーズの練習問題python(上)

121.株を売買する最良の時間I
テーマの内容
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.最大1つの取引(株の購入と売却)しか許可されていない場合は、取得できる最大利益を計算するアルゴリズムを設計します.株を買う前に株を売ってはいけないことに注意してください.
構想
2つの変数,最小購入価格,最大利益を導入し,配列を巡り,最大値と最小値を判断して最後の結果を得た.
コード#コード#

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices)<2:
            return 0
        min_price = prices[0]
        max_profile = 0
        for i in prices:
            min_price = min(min_price, i)
            max_profile = max(max_profile, i - min_price)
        return max_profile

122.株の売買に最適な時間II
タイトル
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
考え方1
Iとの違いは、できるだけ多くの取引ができることです.同様に、複数の取引に参加することはできません.欲張りアルゴリズムを使うことができます.安値で买い取り、后回しに判断して前日より高く売る.その後はこの日の価格を購入し、引き続き後回しに判断します.
コード#コード#

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices)<2:
            return 0
        min_price = prices[0]
        max_profile = 0
        for i in prices:
            if i > min_price:
                max_profile = max_profile + i - min_price
            min_price = i
        return max_profile

考え方2
できるだけ多くの取引を行うには、隣接する2日間の株価を判断し、差が正であれば差を加算して最後の利益を得ることができる.
コード#コード#

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) < 2:
            return 0
        price = prices[0]
        profile = 0
        for i in range(1, len(prices)):
            profile = profile + max(prices[i]-prices[i-1], 0)
        return profile

123.株の売買に最適な時間III
タイトル
配列が与えられ、i番目の要素はi日目の株価である.あなたが得られる最大利益を計算するアルゴリズムを設計します.最大2つの取引を完了することができます.注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
考え方1
これは121題の拡張と考えられるので,配列を前後の2つの部分に分け,前の部分の最大値に後の部分の最大値を加えると全体の最大値となると考えられる.しかし,配列を前後の2つに分ける方式には多くの種類があり,どの分割方式が最大値であるかを判断する必要がある.問題を解く過程で、分割方式を簡単に運用すると、タイムアウトの問題が発生するため、改善を行い、実行可能なコードを得た.コードは以下の通りである.
コード(タイムアウト)

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) < 2:
            return 0
        m = 1
        max_profile3 = prices
        while(True):
            min_price = prices[0]
            max_profile = 0
            for i in range(m):
                min_price = min(min_price, prices[i])
                max_profile = max(max_profile, prices[i]-min_price)
            min_price = prices[m-1]
            max_profile2 = 0
            for j in range(m-1,len(prices)):
                min_price = min(min_price,prices[j])
                max_profile2= max(prices[j]-min_price, max_profile2)
            max_profile3.append(max_profile + max_profile2)
            if m == len(prices):
                break
            m = m + 1
        return max(max_profile3)

このコードでは,1つのループの下に2つのループがあり,コードの複雑さが高すぎるため,簡略アルゴリズムを考慮する.このコードは最後の結果をmax_に書き込みます.profile 3の数列にあります.したがって,2つの配列をそれぞれ定義し,前半の最大値と後半の最大値をそれぞれ2つの配列に書き込み,全体の最大値の判断を1サイクル,3サイクルシリアル,複雑度を減少させることが考えられる.
コード(修正)

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) < 2:
            return 0
        profile1 = [0 for i in range(len(prices))]
        profile2 = [0 for i in range(len(prices))]
        max_profile = 0
        min_price = prices[0]
        max_price = prices[len(prices)-1]
        for i in range(len(prices)):
            min_price = min(min_price, prices[i])
            profile1[i] = max(profile1[i-1], prices[i]-min_price)

        for j in range(len(prices)-1,-1,-1):
            max_price = max(max_price, prices[j])
            profile2[j] = max(profile2[j-1], max_price-prices[j])

        for i in range(len(prices)):
            max_profile = max(max_profile, profile1[i]+profile2[i])

        return max_profile

その後も大神の解法が見られ、ダイナミックプランニングの思想を使って、10行程度のコードで、この部分は次の編で共有されます.