这道题是面试遇到的，显然是个动态规划题。

1.题目

原题：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

例子：

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

2.解析

（1）暴力求解法
这道题的解法最好想的就是暴力求解，复杂度O(n2)，但是要注意买卖只能从买入之后进行所以第二个for循环写i+1就行了。
（2）动态规划法
但是，肯定有更优的方法，比如动态规划就是为了这道题而存在的，一开始我想的是用一个二维列表来做，但是仔细一想，他的复杂度跟暴力差不多啊。后来借鉴网上思路了，用一个一维列表存储截止第k天的最大收益，还有一个变量记录截止昨天的最低买入价格。这样一来时间复杂度为O（n）了。因为是动态规划，所以最大值肯定是最后一个元素，这样就省去排序这一步了。

3.python代码

class Solution:
    def  maxProfit(self, prices):
        if not prices or len(set(prices)) == 1:
            return 0
        m = len(prices)
        maxout = [0]
        minp = prices[0]
        for i in range(1, m):
            maxout.append(max(prices[i] - minp, maxout[i-1]))
            if prices[i] < minp:
                minp = prices[i]
        return maxout[-1]