给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
codeType
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
codeType
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
codeType
1 <= prices.length <= 105
0 <= prices[i] <= 104
解法：
解法一：
python
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
'''
用暴力法的话，就是把数组依次分为两部分，找到前面部分的最小值，和后部分的最大值，时间复杂度为O(n^2),空间复杂度为O(1)
所以可以延伸用动态规划的思想，用两个数组分别存储当前位置下前部分的最小值和后部分的最大值，从而降低时间复杂度O(n)，但是空间复杂度就变成O(n)了。
两个数组对应位置相减，就是所能获得的利润。找到最大值就行。
'''
n = len(prices)
# 初始化最小/最大值数组（提前分配长度，避免索引越界）
minArr = [0] * n
maxArr = [0] * n
minArr[0] = prices[0] # 第一个值肯定是该位置的最小值
maxArr[n - 1] = prices[n - 1] # 最后一个值肯定是该位置的最大值
p1 = 1
p2 = n - 2
while(p1 < n):
minArr[p1] = min(prices[p1], minArr[p1 - 1]) # 和minArr的上一位进行比较就可以
maxArr[p2] = max(prices[p2], maxArr[p2 + 1])
p1 += 1
p2 -= 1
maxP = maxArr[0] - minArr[0]
for i in range(1, n):
maxP = max(maxArr[i] - minArr[i], maxP)
return maxP
解法二：
python
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
n = len(prices)
'''
更进一步的话，我们可以遍历数组，把数组看作只有当前遍历位置的长度，并且记录下当前的最大利润，以及最低价格。
这样就可以将空间复杂度将到O(1)
'''
minprice = prices[0]
maxprofit = 0
for i in range(1,n):
minprice = min(prices[i], minprice) # 更新第i天的最低价
maxprofit = max(prices[i] - minprice, maxprofit) # 更新第i天的最大利润
return maxprofit