买卖股票的最好时机(一)

问题简述

给定一支股票的价格序列，返回买卖一次的最大值；

买卖股票的最好时机(一)_牛客题霸_牛客网

思路：动态规划

• 记 dp[i] 表示 prices[:i] 中的最小值；

• 则 ret = max(x - dp[i])；

• 实际可以用一个变量记录当前最小值，节省空间；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        ret = 0
        min_p = prices[0]
        for x in prices[1:]:
            ret = max(ret, x - min_p)
            min_p = min(x, min_p)
        return ret