[300 Bài Code Thiếu Nhi] Best Time to Buy and Sell Stock – Python

Mô tả bài toán

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Giải pháp

Bạn có thể nghĩ rằng chúng ta có thể tìm cố nhỏ nhất và lớn nhất từ mảng và có thể lấy được lợi nhuận lớn nhất. Những cũng có những ngoại lệ.

Ví dụ:

prices=[3,4,1,6]
min=1
max=6
profit=max-min=5

Điều này là chính xác nhưng ở 1 ví dụ khác:

prices = [7,6,4,3,1]
min = 1 price at day 6
max = 7 price at day 1
max_profit = 7-1 = 6

Điều này đúng nhưng chúng ta không thể mua ở ngày 6 và bán ở ngày 1 được.

Giải pháp ở đây là ta sử dụng 2 con trỏ để trỏ vào 2 vị trí đầu của mảng. Con trỏ 1 để chỉ ngày mua cổ phiếu, con trỏ 2 là ngày bán cổ phiếu. Lợi nhuận ban đầu là 0.

Bắt đầu lặp từ phần tử vị trí con trỏ 2 cho đến hết mảng. Tính lợi nhuận là giá trị của vị trí 2 con trỏ. Nếu lợi nhuận là dương thì thực hiện so sánh lợi nhuận vừa tìm được với lợi nhuận được gán ban đầu và đưa giá trị lớn hơn vào lợi nhuận ban đầu, nếu không thì thực hiện gán con trỏ 1 = con trỏ 2. Tịnh tiến con trỏ 2 lên 1.

Sau khi thực hiện hết vòng lặp ta sẽ lấy được lợi nhuận lớn nhất.

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        left = 0;
        right = 1;
        max_profit = 0;
        while(right < len(prices)):
            currentProfit = prices[right] - prices[left];
            if(currentProfit > 0):
                max_profit = max(currentProfit, max_profit);
            else:
                left = right;
            right += 1;
        return max_profit;

You need to login in order to like this post: click here