สมมติว่าเรามีรายการราคาที่แสดงราคาหุ้นของบริษัทตามลำดับเวลา เราต้องหากำไรสูงสุดที่เราสามารถทำได้จากการซื้อและขายหุ้นนั้นหลายครั้ง เราต้องจำไว้ว่าเราต้องซื้อก่อนจึงจะขายได้
ดังนั้น หากอินพุตเป็นเหมือนราคา =[10, 50, 30, 40, 60] ผลลัพธ์จะเป็น 70 ตามที่เราสามารถซื้อได้ที่ 10 ขายที่ 50 ซื้อที่ 30 และขายที่ 60
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- prev_price :=อินฟินิตี้
- กำไร :=0
- สำหรับแต่ละ p ในราคา ทำ
- ถ้า p>
prev_price แล้ว
- กำไร :=กำไร + p - prev_price
- prev_price :=p
- ถ้า p>
prev_price แล้ว
- คืนกำไร
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def solve(self, prices):
prev_price = float("inf")
profit = 0
for p in prices:
if p > prev_price:
profit += p - prev_price
prev_price = p
return profit
ob = Solution()
print(ob.solve([10, 50, 30, 40, 60])) อินพุต
[10, 50, 30, 40, 60]
ผลลัพธ์
70
