home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

Best Time to Buy and Sell Stock III ใน Python

กำหนดอาร์เรย์ราคาหุ้นวันละ i ต้องหากำไรสูงสุดได้สูงสุด 2 transactions (ซื้อ-ขาย)

ตัวอย่าง: [3,3,5,0,1,3,1,4] → 6 (ซื้อวันที่ 4 ราคา 0 ขายวันที่ 6 ราคา 3 กำไร 3; ซื้อวันที่ 7 ราคา 1 ขายวันที่ 8 ราคา 4 กำไร 3)

ขั้นตอนการแก้ปัญหา

  • Forward pass: คำนวณ max profit ถ้าขายในวัน i (dp[i])
  • Backward pass: คำนวณ max profit ถ้าซื้อในวัน i (xmax[i])
  • รวม: สำหรับแต่ละวัน i พิจารณา dp[i] + max profit หลังวันที่ i

ตัวอย่างโค้ด

class Solution(object):
    def maxProfit(self, p):
        if not p:
            return 0
        n = len(p)
        dp = [0] * 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] * n
        xmax[-1] = p[-1]
        tempp = 0
        for i in range(n-2, -1, -1):
            xmax[i] = max(xmax[i+1], p[i])
        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