Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมหากำไรสูงสุดที่เราสามารถทำได้หลังจาก k Buy and Sell ใน python


สมมุติว่าเรามีรายการตัวเลขที่เรียกว่า nums ที่แทนราคาหุ้นของบริษัทหนึ่งๆ ตามลำดับเวลาและเรายังมีค่า k อีกค่าหนึ่งด้วย เราต้องหากำไรสูงสุดที่เราสามารถทำได้จากการซื้อและขายสูงสุด k (เราต้องซื้อ) ก่อนขายและขายก่อนซื้อ)

ดังนั้น หากอินพุตเป็นเหมือนราคา =[7, 3, 5, 2, 3] k =2 แล้วผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถซื้อที่ 3 แล้วขายที่ 5 ซื้ออีกครั้งที่ 2 แล้วขาย ที่ 3.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, k, ซื้อแล้ว
  • ถ้าฉันเท่ากับขนาดของราคาหรือ k เท่ากับ 0 แล้ว
    • คืน 0
  • ถ้าซื้อจริงก็
    • ผลตอบแทนสูงสุดของ (dp(i+1, k-1, False) + ราคา[i]) และ dp(i+1, k, ซื้อแล้ว)
  • มิฉะนั้น
    • ผลตอบแทนสูงสุดของ (dp(i+1, k, True) - ราคา[i]) และ dp(i + 1, k, ซื้อแล้ว)
  • จากการเรียกเมธอดหลัก dp(0, k, False) และส่งคืนผลลัพธ์

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, prices, k):
      def dp(i, k, bought):
         if i == len(prices) or k == 0:
            return 0
         if bought:
            return max(dp(i + 1, k - 1, False) + prices[i], dp(i + 1, k, bought))
         else:
            return max(dp(i + 1, k, True) - prices[i], dp(i + 1, k, bought))

      return dp(0, k, False)

ob = Solution()
prices = [7, 3, 5, 2, 3]
k = 2
print(ob.solve(prices, k))

อินพุต

[7, 3, 5, 2, 3], 2

ผลลัพธ์

3