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

Giả sử chúng ta có mảng giá cổ phiếu trong đó phần tử thứ i là giá ngày i. Tìm lợi nhuận tối đa với tối đa 2 giao dịch. Ví dụ: [3,3,5,0,1,3,1,4] -> kết quả 6 (mua ngày 4 giá 0, bán ngày 6 giá 3; mua ngày 7 giá 1, bán ngày 8 giá 4).

Các bước giải quyết (Dynamic Programming):

• Tính dp[i] = lợi nhuận tối đa 1 giao dịch từ đầu đến ngày i
• Tính xmax[i] = giá lớn nhất từ ngày i đến cuối
• Duyệt ngược: tempp = lợi nhuận tối đa 1 giao dịch từ ngày i đến cuối
• Kết hợp: ans = max(ans, dp[i] + tempp)

Ví dụ

class Solution(object):
    def maxProfit(self, p):
        if not p:
            return 0
        n = len(p)
        dp = [0 for i in range(n)]
        ans = 0
        xmin = p[0]
        for i in range(1, n):
            xmin = min(xmin, p[i])
            dp[i] = max(dp[i], p[i] - xmin)
            ans = max(ans, dp[i])
        xmax = [0 for i in range(n)]
        xmax[-1] = p[-1]
        tempp = 0
        for i in range(n-2, -1, -1):
            xmax[i] = max(xmax[i+1], p[i])
        for i in range(n-2, -1, -1):
            tempp = max(tempp, xmax[i+1] - p[i+1])
            ans = max(ans, dp[i] + tempp)
        return ans

ob = Solution()
print(ob.maxProfit([3, 3, 5, 0, 1, 3, 1, 4]))

Đầu vào

[3, 3, 5, 0, 1, 3, 1, 4]

Đầu ra

6