Giả sử chúng ta có một danh sách 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 đó. Chúng ta phải mua trước khi bán và phải đợi một ngày sau khi bán cổ phiếu trước khi mua lại.
Vì vậy, nếu đầu vào giống như giá =[2, 6, 9, 4, 11], thì đầu ra sẽ là 11, vì chúng ta có thể mua ở mức 2, sau đó bán ở mức 6, chờ một ngày, sau đó mua ở mức 4 và sau đó bán với giá 11.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
s:=0
-
b:=-infinity
-
đối với tôi trong phạm vi từ 0 đến kích thước của giá cả, hãy làm
-
tạm thời:=b
-
b:=tối đa của b và (s - giá [i])
-
nếu tôi khác 0, thì
-
s:=tối đa của s và (tạm thời + giá [i - 1])
-
-
-
trả về tối đa s và (b + phần tử cuối cùng của giá)
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):
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)) Đầu vào
[2, 6, 9, 4, 11]
Đầu ra
11