Thời điểm tốt nhất mua bán cổ phiếu trong Python

Cho mảng giá A[i]. Tối đa một giao dịch (mua một lần, bán một lần). Tìm lợi nhuận max. Ví dụ: [7,1,5,3,6,4] → 5 (mua giá 1, bán giá 6).

Giải pháp

Dùng mảng leftMin (min từ đầu đến i) và rightMax (max từ i đến cuối):

• leftMin[0]=A[0]; leftMin[i]=min(leftMin[i-1],A[i]).
• rightMax[n-1]=A[n-1]; rightMax[i]=max(rightMax[i+1],A[i]).
• ans = max(rightMax[i+1]-leftMin[i]) với i từ 0 đến n-2.

Ví dụ

Triển khai Python:

class Solution(object): 
    def maxProfit(self, prices): 
        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]) 
        rightMax[-1]= prices[-1] 
        for i in range(len(prices)-2,-1,-1): 
            rightMax[i] = max(rightMax[i+1],prices[i]) 
        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