สมมติว่าเรามีรายการราคาหุ้นของบริษัทตามลำดับเวลา เราต้องหากำไรสูงสุดที่เราสามารถทำได้จากการซื้อและขายหุ้น เราต้องซื้อก่อนขาย และเราต้องรอหนึ่งวันหลังจากขายหุ้นก่อนซื้อใหม่
ดังนั้นหากอินพุตเป็นเหมือนราคา =[2, 6, 9, 4, 11] แล้วผลลัพธ์จะเป็น 11 ตามที่เราสามารถซื้อได้ที่ 2 แล้วขายที่ 6 รอวันแล้วซื้อที่ 4 และ แล้วขายตอน 11 โมง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
s :=0
-
b :=-อินฟินิตี้
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาดของราคาทำ
-
อุณหภูมิ :=b
-
b :=สูงสุดของ b และ (s - ราคา[i])
-
ถ้าฉันไม่เป็นศูนย์แล้ว
-
s :=สูงสุดของ s และ (ชั่วคราว + ราคา[i - 1])
-
-
-
คืนค่าสูงสุดของ s และ (b + องค์ประกอบสุดท้ายของราคา)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution:
def solve(self, prices):
s = 0
b = float("-inf")
for i in range(len(prices)):
temp = b
b = max(b, s - prices[i])
if i:
s = max(s, temp + prices[i - 1])
return max(s, b + prices[-1])
ob = Solution()
prices = [2, 6, 9, 4, 11]
print(ob.solve(prices)) อินพุต
[2, 6, 9, 4, 11]
ผลลัพธ์
11
