买卖股票的最佳时机

image.png

简单题，第一思路是双重循环找价格最大差值，但时间复杂度O(n^2), 会超时。

优化版思路，利用简单动态规划。dp获得前i天的最低买入值，然后实时更新第i天卖出能获得最大收益。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        # 维护一个前i天的最低买入值
        dp = [0 for i in range(n)]
        dp[0] = prices[0]
        maxin = 0
        for i in range(1,n):
          dp[i]=min(dp[i-1],prices[i])
          maxin = max(maxin,prices[i]-dp[i])
        return maxin