题目难度：简单
默认优化目标：最小化平均时间复杂度。
Python默认为Python3。
目录
1 题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
-
1 <= prices.length <= 105 -
0 <= prices[i] <= 104
2 题目解析
输入是一个数组prices，输出是最大利润，即price中两个元素之间最大的差值。约束条件是要后一天的价格减去前一天的价格。
3 算法原理及程序实现
3.1 暴力求解
我们使用双重循环，外循环用于遍历元prices中元素，内循环用于比较当前元素和其后面所有元素的差值。在所有差值中找到最大的，即题目要求的输出。
平均时间复杂度为O(n^2)，平均空间复杂度为O(1)。
C++代码实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit=0;
int n=prices.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
profit=max(profit,prices[j]-prices[i]);
}
}
return profit;
}
};Python代码实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n=len(prices)
profit=0
for i in range(n):
for j in range(i+1,n):
profit=max(profit,prices[j]-prices[i])
return profit3.2 动态规划
举个例子，现在prices=[8,3,5,7,4,6,4]，折线图如下。
买卖股票，无非是低点买进，高点卖出。最理想呢，是最低点买进，最高点卖出。问题就拆分成，寻找价格的最低点，然后用最低点后面的价格去减，取最大的差值。
这个过程是动态的，且只需要一次循环就能完成。还是以prices=[8,3,5,7,4,6,4]的例子说明。我们记最小值为minprice，记利润为profit，记当前元素为price。首先，给minprice赋个极大值，初始化profit=0。第一次，price=8，我们让price-minprice，然后和profit比大小，取最大值。明显profit=0。然后，让price和minprice比大小，取最小的那个，minprice=8。第二次，price=3，profit=0,minprice=3。第三次，price=5，profit=2，minprice=3。第四次，price=7，profit=4，minprice=3。第五次，price=4，profit=4，minprice=3。第六次，price=6，profit=4，minprice=3。第七次，price=4，profit=4，minprice=3。
价格最低点是在动态更新的，利润也在动态更新。由于我们只遍历一遍全部元素，当找到最小值时，和它相减的价格必然出现在这个最小值之后。满足后一天的价格减去前一天的价格这个约束。
平均时间复杂度为O(n)，平均空间复杂度为O(1)。
C++代码实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit=0;
int minprice=1e9;
for(int price: prices){
profit=max(profit,price-minprice);
minprice=min(minprice,price);
}
return profit;
}
};Python代码实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit=0
minprice=int(1e9)
for price in prices:
profit=max(profit,price-minprice)
minprice=min(minprice,price)
return profit