Chương trình tìm lợi nhuận tối đa mua bán cổ phiếu nắm giữ nhiều ngày Python

Cho mảng nums giá cổ phiếu theo thời gian. Mỗi ngày có thể mua tối đa 1 cổ phiếu, có thể nắm giữ nhiều cổ phiếu cùng lúc, bán bất kỳ ngày nào. Tìm lợi nhuận tối đa.

Ví dụ: nums=[3,4,7,3,5] → 9 (mua 3,4 bán 7; mua 3 bán 5 → (7-3)+(7-4)+(5-3)=9).

Giải thuật (Duyệt ngược - Tìm đỉnh cục bộ)

1. Duyệt từ cuối mảng về đầu
2. Giữ top = giá cao nhất thấy được từ phải sang
3. Khi thấy giá top > giá hiện tại → bán tại top, lợi nhuận += top - current
4. Khi thấy giá mới cao hơn top → cập nhật top

Ví dụ triển khai

def solve(nums):
    ans = 0
    while nums:
        top = nums.pop()
        while nums and top > nums[-1]:
            ans += top - nums.pop()
    return ans

print(solve([3, 4, 7, 3, 5]))

Đầu vào

[3, 4, 7, 3, 5]

Đầu ra

9