Pythonで株式を売買するのに最適な時期

配列Aがあるとします。ここで、A[i]はi日目の特定の株式の価格を示しています。最大の利益を見つけなければなりません。最大で1つのトランザクションを完了できます。 （取引とは、株式を売買することを意味します）。ただし、同時に複数の取引を行うことはできませんのでご注意ください。そのため、新しい株を購入する前に株を売る必要があります。

配列がA=[7、1、5、3、6、4]のようであるとすると、結果は5になります。ご覧のとおり、2日目（インデックス1）に購入すると、1は次のようになります。購入価格。次に、5日目に販売すると、利益は6 – 1=5になります。

これを解決するには、次の手順に従います-

• Aと同じサイズの2つの配列leftMinとrightMaxを作成し、それらを0で埋めます
• leftMin [0] =A [0]
• 範囲1からA– 1の長さのiの場合、leftMin [i] =leftMin [i –1]とA[i]の最小値
• rightMax [n-1] =A [n – 1]
• A – 1から1までの範囲のiの場合、rightMax [i] =rightMax [i+1]およびA[i]の最大値
• 答えを設定：=0
• 範囲0からA– 1の長さのiの場合、回答：=回答の最大値およびrightMax [i + 1] – leftMin [i]
• 回答を返す

理解を深めるために実装を見てみましょう

例

class Solution(object):
   def maxProfit(self, prices):
      """
      :type prices: List[int]
      :rtype: int
      """
      if not prices:
         return 0
      leftMin,rightMax = [0 for i in range(len(prices))],[0 for i in range(len(prices))]
      leftMin[0] = prices[0]
      for i in range(1,len(prices)):
         leftMin[i] = min(leftMin[i-1],prices[i])
      #print(leftMin)
      rightMax[-1]= prices[-1]
      for i in range(len(prices)-2,-1,-1):
         rightMax[i] = max(rightMax[i+1],prices[i])
      #print(rightMax)
      ans = 0
      for i in range(len(prices)-1):
         ans = max(ans,rightMax[i+1]-leftMin[i])
      return ans
ob1 = Solution()
print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))

入力

prices = [7,2,5,8,6,3,1,4,5,4,7]

出力

6