leetcode121-- Best Time to Buy and Sell Stock I

leetcode121-- Best Time to Buy and Sell Stock I

题目

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.



即只能买一次也只能卖一次,问最大利润是什么?

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        # DP
        # ret来存最大profit,minimum 代表第i天之前的最低价格,
        
        if len(prices) <2:
            return 0
        ret = 0
        minimum = prices[0]
        
        for x in prices[1:]:
            ret = max(ret, x-minimum)  # 更新最大利润
            minimum = min(minimum, x)  # 更新之前的最低价格
            
        return ret

注意每次都是要先更新最大利润,后更新最小的价格,最小的价格初始化为第一天的价格.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦