题目描述

给一个数组prices[]，prices[i]代表股票在第i天的售价，求出只做一次交易(一次买入和卖出)能得到的最大收益。

我的解法——DP

prices[i]代表第i天卖、第i天之前的某一天买的话，获得的最大收益。
即固定“卖”来找“买”，本质上是双指针思路
n的复杂度。
结果：beat 70.15%

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if(len(prices) == 0):
            return 0
        smallest = prices[0]
        res = 0
        for i in range(len(prices)):
            if(prices[i] < smallest):
                smallest = prices[i]
            prices[i] = prices[i] - smallest
            if(prices[i] > res):  # 一边循环，避免循环两遍
                res = prices[i]

        return res

参考答案

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/solution/