โปรแกรมหากำไรสูงสุดจากการถือและขายหุ้นใน Python

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

เช่น ถ้าอินพุตคือ nums = [3, 4, 7, 3, 5] ผลลัพธ์จะเป็น 9 เพราะซื้อที่ 3 และ 4 แล้วขายที่ 7 แล้วซื้อที่ 3 ขายที่ 5 กำไรรวม (7-3) + (7-4) + (5-3) = 9

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

1. ans := 0
2. ในขณะที่ nums ไม่ว่าง:
   • top := นำสมาชิกสุดท้ายออกจาก nums
   • ในขณะที่ nums ไม่ว่าง และ top > nums[-1]:
     • ans := ans + (top - nums.pop())
3. คืนค่า ans

ตัวอย่างการใช้งาน

def solve(nums):
    ans = 0
    while nums:
        top = nums.pop()
        while nums and top > nums[-1]:
            ans += top - nums.pop()
    return ans

nums = [3, 4, 7, 3, 5]
print(solve(nums))

อินพุต

[3, 4, 7, 3, 5]

เอาต์พุต

9