问题描述

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

解题思路

买卖股票的最佳时机是一个系列，这是最简单的一个题目。

首先我们定义一个dp数组，数组中元素的含义是，dp[i]代表了第i天为止能够获得的最大收益。

我们买卖股票的核心逻辑，就是低价买入高价卖出。所以我们要记录一个变量，来记住当天之前最低的股票价格。

所以状态转移方程就是dp[i] = max(dp[i-1], prices[i]-min_price)

dp[i-1]当然就是代表了今天不卖股票（卖还是不卖，由max决定）。

代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp[i]为当天的最大利润
        dp = [0 for i in range(len(prices))]
        min_price = prices[0]
        for i in range(1, len(prices)):
            min_price = min(min_price, prices[i])
            dp[i] = max(dp[i-1], prices[i]-min_price)
        return max(dp)