Thời điểm tốt nhất để mua và bán cổ phiếu III bằng Python

Giả sử chúng ta có một mảng mà phần tử thứ i đại diện cho giá của một cổ phiếu nhất định vào ngày thứ i. Chúng tôi phải nghĩ ra một thuật toán để tìm ra lợi nhuận tối đa. Chúng tôi có thể hoàn thành nhiều nhất hai giao dịch. Vì vậy, nếu các mức giá đã cho là [3,3,5,0,1,3,1,4], thì kết quả sẽ là 6, vì chúng ta sẽ mua vào ngày 4 (giá 0), sau đó bán vào ngày 6, ( giá 3), như vậy lợi nhuận là 3 - 0 =3. Bây giờ nhưng là ngày thứ 7 (giá 1) và bán vào ngày thứ 8 (giá 4) nên lợi nhuận là 4 - 1 =3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s, m:=kích thước của t. Cập nhật s và t bằng cách nối các khoảng trắng trước chúng

• Tạo một ma trận có kích thước (n + 1) x (m + 1)

• đặt dp [0, 0]:=1, sau đó đặt 1 cho cột thứ 0 của tất cả hàng, đặt 1

• cho tôi trong phạm vi từ 1 đến n

  • đối với j trong phạm vi từ 1 đến m

    • nếu s [i] =t [j] thì

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

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

• trả về dp [n, m]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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]))

Đầu vào

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

Đầu ra

6