สมมุติว่าเรามีรายการตัวเลขที่เรียกว่าราคา และนั่นเป็นการแสดงราคาหุ้นของบริษัทหนึ่งๆ ตามลำดับ เราต้องหากำไรสูงสุดที่เราสามารถทำได้จากการซื้อและขายหุ้นนั้นไม่เกินสองครั้ง เราต้องซื้อก่อนแล้วค่อยขาย
ดังนั้นหากอินพุตเป็นเหมือนราคา =[2, 6, 3, 4, 2, 9] แล้วผลลัพธ์จะเป็น 11 เนื่องจากเราสามารถซื้อได้ที่ราคา 2 จากนั้นขายที่ 6 ซื้ออีกครั้งที่ 2 แล้วขาย เวลา 9.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- first_buy :=-inf, first_sell :=-inf
- second_buy :=-inf, second_sell :=-inf
- สำหรับราคาแต่ละพิกเซล ทำ
- first_buy :=สูงสุดของ first_buy และ -px
- first_sell :=สูงสุดของ first_sell และ (first_buy + px)
- second_buy :=สูงสุดของ second_buy และ (first_sell - px)
- second_sell :=สูงสุดของ second_sell และ (second_buy + px)
- ผลตอบแทนสูงสุด 0, first_sell และ second_sell
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def solve(self, prices):
first_buy = first_sell = float("-inf")
second_buy = second_sell = float("-inf")
for px in prices:
first_buy = max(first_buy, -px)
first_sell = max(first_sell, first_buy + px)
second_buy = max(second_buy, first_sell - px)
second_sell = max(second_sell, second_buy + px)
return max(0, first_sell, second_sell)
ob = Solution()
prices = [2, 6, 3, 4, 2, 9]
print(ob.solve(prices)) อินพุต
[2, 6, 3, 4, 2, 9]
ผลลัพธ์
11
