เวลาที่ดีที่สุดในการซื้อและขายหุ้น III ใน Python

สมมติว่าเรามีอาร์เรย์ที่องค์ประกอบ ith แสดงถึงราคาของหุ้นที่กำหนดในวันที่ i เราต้องสร้างอัลกอริทึมเพื่อหากำไรสูงสุด เราสามารถทำธุรกรรมได้ไม่เกินสองรายการ ดังนั้นหากราคาที่กำหนดคือ [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)

• set dp[0, 0] :=1 จากนั้นตั้งค่า 1 สำหรับคอลัมน์ที่ 0 ของแถวทั้งหมด ใส่ 1

• สำหรับฉันอยู่ในช่วง 1 ถึง n

  • สำหรับ j ในช่วง 1 ถึง m

    • ถ้า 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