파이썬에서 주식 III를 사고 팔기 가장 좋은 시기

i번째 요소가 i일의 주어진 주식 가격을 나타내는 배열이 있다고 가정합니다. 우리는 최대 이익을 찾는 알고리즘을 고안해야 합니다. 최대 2개의 거래를 완료할 수 있습니다. 따라서 주어진 가격이 [3,3,5,0,1,3,1,4]인 경우 결과는 6이 됩니다. 4일차(가격 0)에 매수하고 6일차에 매도( 가격 3), 따라서 이익은 3 – 0 =3입니다. 지금은 7일차(가격 1)에 판매되고 8일차(가격 4)에 판매되므로 이익은 4 – 1 =3입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=s의 크기, m :=t의 크기. s와 t 앞에 공백을 연결하여 업데이트합니다.

• (n + 1) x (m + 1) 크기의 행렬 하나 만들기

• dp[0, 0] :=1로 설정한 다음 모든 행의 0번째 열에 1을 설정하고 1

• 범위 1에서 n까지의 i에 대해

  • 범위 1에서 m까지의 j에 대해

    • s[i] =t[j]이면

      • dp[i, j] :=dp[i – 1, j – 1]

    • dp[i, j] :=dp[i, j] + dp[i – 1, j]

• 반환 dp[n, m]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def maxProfit(self, p):
      if not p:
         return 0
      n = len(p)
      dp = [0 for i in range(n)]
      ans = 0
      xmin = p[0]
      for i in range(1,n):
         xmin = min(xmin,p[i])
         dp[i] = max(dp[i],p[i]-xmin)
         ans = max(ans,dp[i])
      xmax = [0 for i in range(n)]
      xmax[-1] =p[-1]
      tempp = 0
      for i in range(n-2,-1,-1):
         xmax[i] = max(xmax[i+1],p[i])
      xmin = [p[-1],n]
      for i in range(n-2,-1,-1):
         tempp = max(tempp,xmax[i+1]-p[i+1])
         ans = max(ans,dp[i]+tempp)
      return ans
ob = Solution()
print(ob.maxProfit([3,3,5,0,1,3,1,4]))

입력

[3,3,5,0,1,3,1,4]

출력

6