Giả sử chúng ta có một mảng A, ở đây A [i] cho biết giá của một cổ phiếu nhất định vào ngày thứ i. Chúng ta phải tìm ra lợi nhuận tối đa. Chúng tôi có thể hoàn thành nhiều nhất một giao dịch. (Giao dịch có nghĩa là mua và bán cổ phiếu). Nhưng chúng ta phải lưu ý rằng chúng ta không được tham gia vào nhiều giao dịch cùng một lúc. Vì vậy, chúng tôi phải bán cổ phiếu trước khi mua cổ phiếu mới.
Giả sử mảng giống như A =[7, 1, 5, 3, 6, 4] thì kết quả sẽ là 5. Như chúng ta thấy, nếu chúng ta mua vào ngày thứ 2 (chỉ số 1), thì nó sẽ mất 1 như giá mua. Sau đó, nếu chúng tôi bán vào ngày thứ 5, lợi nhuận sẽ là 6 - 1 =5.
Để giải quyết vấn đề này, hãy làm theo các bước sau -
- tạo hai mảng leftMin và rightMax có cùng kích thước như A và điền chúng bằng các chữ số 0
- leftMin [0] =A [0]
- đối với tôi trong phạm vi từ 1 đến độ dài là A - 1, leftMin [i] =tối thiểu leftMin [i - 1] và A [i]
- rightMax [n-1] =A [n - 1]
- đối với tôi trong phạm vi độ dài từ A - 1 giảm xuống 1, rightMax [i] =tối đa rightMax [i + 1] và A [i]
- đặt câu trả lời:=0
- đối với tôi trong phạm vi từ 0 đến độ dài là A - 1, answer:=max of answer và rightMax [i + 1] - leftMin [i]
- trả lời câu trả lời
Hãy cho chúng tôi xem việc triển khai để hiểu rõ hơn
Ví dụ
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if not prices: return 0 leftMin,rightMax = [0 for i in range(len(prices))],[0 for i in range(len(prices))] leftMin[0] = prices[0] for i in range(1,len(prices)): leftMin[i] = min(leftMin[i-1],prices[i]) #print(leftMin) rightMax[-1]= prices[-1] for i in range(len(prices)-2,-1,-1): rightMax[i] = max(rightMax[i+1],prices[i]) #print(rightMax) ans = 0 for i in range(len(prices)-1): ans = max(ans,rightMax[i+1]-leftMin[i]) return ans ob1 = Solution() print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))
Đầu vào
prices = [7,2,5,8,6,3,1,4,5,4,7]
Đầu ra
6