image.png

簡單題，第一思路是雙重循環(huán)找價格最大差值，但時間復雜度O(n^2), 會超時。

優(yōu)化版思路，利用簡單動態(tài)規(guī)劃。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