Giả sử chúng ta có một danh sách các con số được gọi là giá và đại diện cho giá cổ phiếu của một công ty theo thứ tự thời gian, chúng ta phải tìm lợi nhuận tối đa mà chúng ta có thể kiếm được từ việc mua và bán cổ phiếu đó nhiều nhất hai lần. Chúng ta phải mua trước rồi mới bán.
Vì vậy, nếu đầu vào giống như giá =[2, 6, 3, 4, 2, 9], thì đầu ra sẽ là 11, vì chúng ta có thể mua ở mức giá 2, sau đó bán ở mức 6, lại mua ở mức 2 và bán lúc 9.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- first_buy:=-inf, first_sell:=-inf
- second_buy:=-inf, second_sell:=-inf
- đối với mỗi px trong giá, hãy thực hiện
- first_buy:=tối đa là first_buy và -px
- first_sell:=tối đa first_sell và (first_buy + px)
- second_buy:=tối đa second_buy và (first_sell - px)
- second_sell:=tối đa second_sell và (second_buy + px)
- trả về tối đa 0, first_sell và second_sell
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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)) Đầu vào
[2, 6, 3, 4, 2, 9]
Đầu ra
11