5/26每日一題(實現最大利潤,先買後賣)

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.

 

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

class Solution:

    def maxProfit(self, prices: List[int]) -> int:

       

        max_fit=0  #如果沒有利潤就回傳0

        min_price=float('inf') #給定一個跟當天price比較用的值

        for price in prices:

            min_price=min(min_price,price)

            #找出最小價格

            max_fit = max(max_fit,price - min_price)

            #比較出最大利潤

        return max_fit

       

       

        # for n, i in enumerate(prices):

        #     if n<len(prices)-1 :

        #         res=max(prices[n+1:])-i

#這邊使用了切片導致運算效能浪費,每次迭代都會重複計算

#時間複雜度是O(n^2) ,所以未通過後面時間限制的測試,而上面代碼時間複雜度是O(n)

        #         m=max(res,m)

        # return m