78. Best Time to Buy and Sell Stock II

5564 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ
  • 回以上の取引所が生み出す最大の利益を計算した.


    • 1.階調アルゴリズム（76 ms）

    

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        
        #값이 오르는 경우 매번 그리디 계산
        for i in range(len(prices) - 1):
            if i in range(len(prices) - 1):
                if prices[i + 1] > prices[i]:
                    result += prices[i + 1] - prices[i]
        return result
  • 12号の「株を売買する好機」問題の第2弾問題は、何度も取引ができる点が異なる.

    この問題は1回の取引しかないので、低点と高点だけチェックしました.

  • 今では何度も取引ができます.

  • 解法は下がる前に売って、上がる前に買うことができます.

  • 現実的には不可能ですが、この問題で次の上げ下げの可否を事前に知ることができ、手数料もないので何度か取引できます.
  • の「貪欲」な意味にぴったりのグリディアルゴリズムの問題と言える.
    • ＜複数回取引の最大収益＞

  • 次は値上げして買って、次は値下げして売って、いつも絵を買って売っているように変えます.
  • 次の値が現在より高い場合は、常に利益を得る形で実際のコードを実現すればよい.
  • が上昇を続けている場合、何度でも売買できるため、一歩一歩が利益をむさぼる貪欲な構造に現れる.

    • 2.ダウンジャケット（72ミリ秒）

    

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #0보다 크면 무조건 합산
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))

  • 以前の回答は段階的に値上げされたのか、毎回比較的に回答しています.

  • しかし、よく考えてみると、計算される利益が0より大きいたびに、無条件に合計することができます.
  • も同様に貪欲な構造であり、同様の結果を得ることができる.
    • TIL 40最初のSolo Day
    Pythonネーミングスペースの理解