Giả sử chúng ta có một danh sách các số được gọi là num, đại diện cho giá cổ phiếu của một công ty theo thứ tự thời gian. Chúng tôi có thể mua nhiều nhất một cổ phiếu mỗi ngày, nhưng bạn có thể giữ nhiều cổ phiếu và có thể bán cổ phiếu vào bất kỳ số ngày nào. Trả lại lợi nhuận tối đa bạn có thể kiếm được.
Vì vậy, nếu đầu vào giống như nums =[3, 4, 7, 3, 5], thì đầu ra sẽ là 9, bởi vì chúng ta có thể mua các cổ phiếu ở mức 3 và 4 và bán chúng ở mức 7. Sau đó lại mua ở mức 3 và bán với giá 5. Tổng lợi nhuận (7 - 3) + (7 - 4) + (5 - 3) =9.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ans:=0
- trong khi nums không trống, hãy thực hiện
- top:=xóa phần tử cuối cùng khỏi nums
- while nums không trống và ở trên cùng> phần tử cuối cùng của nums, hãy thực hiện
- ans:=ans + (phần tử trên cùng - cuối cùng từ nums)
- xóa phần tử cuối cùng khỏi nums
- trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(nums): ans = 0 while nums: top = nums.pop() while nums and top > nums[-1]: ans += top - nums.pop() return ans nums = [3, 4, 7, 3, 5] print(solve(nums))
Đầu vào
[3, 4, 7, 3, 5]
Đầu ra
9