算法思想一：暴力法

解题思路：

需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。
形式上，对于每组 i 和 j（其中 j>i）我们需要找出 max(prices[j]−prices[i])

代码展示:

Python版本 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        res = 0
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                res = max(res, prices[j] - prices[i])
        return res

复杂度分析：

时间复杂度O(N^2)：循环了 n(n-1) / 2次
空间复杂度O(1)：一个变量空间

算法思想二：动态规划

解题思路：

买卖股票有约束，根据题目意思，有以下两个约束条件：
    条件 1：你不能在买入股票前卖出股票；
    条件 2：最多只允许完成一笔交易。
因此 当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把 是否持股 设计到状态数组中

状态定义：
dp[i][j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数。
    j = 0，表示当前不持股；
    j = 1，表示当前持股。
注意：这个状态具有前缀性质，下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息，因此最后输出 dp[len - 1][0]

推导状态转移方程：
dp[i][0]：规定了今天不持股，有以下两种情况：
    昨天不持股，今天什么都不做；
    昨天持股，今天卖出股票（现金数增加），
    状态转移方程：dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1]：规定了今天持股，有以下两种情况：
    昨天持股，今天什么都不做（现金数与昨天一样）；
    昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）
    状态转移方程：dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
代码展示： 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        length = len(prices)
        if length <2:
            return 0
        dp = [[0]*2]*(length)
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1,length):
            dp[i][0] =  max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1] = max(dp[i-1][1],-prices[i])
        return dp[length-1][0]

复杂度分析：

时间复杂度O(N)：只需要遍历一次
空间复杂度O(1)：使用常数级变量空间

算法思想三：一次遍历

解题思路：

1、使用变量记录历史最低价格 minprice
2、则在第 i 天卖出股票能得到的利润就是 prices[i] - minprice
3、因此，我们只需要遍历价格数组一遍，记录历史最低点

代码展示：

Python版本 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        # 初始化最大值
        inf = int(1e9)
        minprice = inf
        maxprofit = 0
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            # 找到最低股票价格
            minprice = min(price, minprice)
        return maxprofit

复杂度分析：

时间复杂度O(N)：只需要遍历一次
空间复杂度O(1)：使用常数级变量空间


参考资料：