题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
暴力法
双层循环
高低谷想法
记录最高值和最低值
我的直观想法
这是我第一次尝试写出来的代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if prices == []: return 0
# profit[][]
profit = [[0,0] for i in prices]
profit[0][0] = 0 # 假如上一次卖了能够获得的利润 和 下面的 大者 ，
# 本质上profit[i][0]表示交易以今天结尾和不以今天结尾 哪个利润大
profit[0][1] = 0 # 上次买直到今天获得的利润，和0的 大者,如果是0，表示今天重新买入，
# 本质上profit[i][1]表示的是以 i 为结尾的交易能够获得的利润
for i in range(1,len(prices)):
profit[i][1] = max(profit[i-1][1]+prices[i]-prices[i-1],0)
profit[i][0] = max(profit[i-1][0],profit[i][1])
print(profit[i][0],profit[i][1])
return profit[-1][0]
但是如果看一下题解，会发现逻辑更强的推导。
以下为抄录题解
这是一个最大连续子数组和的问题。有同学会问，这是怎么看出来的，因为在数组中求两点的差，而两点之差可以转换成求和问题。也许你还是一脸懵，这怎么想的到。如果你学过高等数学，对牛顿莱布尼茨公式有印象的话：
只不过，在我这里，F() 函数不是连续的，而是离散化的，aaa 和 bbb 表示数组的下标。但是这不影响我们得出正确的结论。
总结下：区间和可以转换成求差的问题，求差问题，也可以转换成区间和的问题。
在上面的公式中，我们把 F()F()F() 表示的数组称为前缀和。
最大连续子数组和可以使用动态规划求解， dp[i]dp[i]dp[i] 表示以 iii 为结尾的最大连续子数组和，递推公式为：
版本一：
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) return 0;
vector<int> diff(prices.size() - 1);
for (int i = 0; i < prices.size() - 1; ++i) {
diff[i] = prices[i+1] - prices[i]; # 把序列转换为差
}
vector<int> dp(diff.size());
dp[0] = max(0, diff[0]);
int profit = dp[0];
for (int i = 1; i < diff.size(); ++i) {
dp[i] = max(0, dp[i-1] + diff[i]);
profit = max(profit, dp[i]);
}
return profit;
}
作者：ivan_allen
链接：https://leetcode-cn.com/problems/two-sum/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
版本二：
dp 数组可以被优化掉
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) return 0;
vector<int> diff(prices.size() - 1);
for (int i = 0; i < prices.size() - 1; ++i) {
diff[i] = prices[i+1] - prices[i];
}
int last = 0;
int profit = last;
for (int i = 0; i < diff.size(); ++i) {
last = max(0, last + diff[i]);
profit = max(profit, last);
}
return profit;
}
作者：ivan_allen
链接：https://leetcode-cn.com/problems/two-sum/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
版本三：
diff 数组也可以被优化掉
int maxProfit(vector<int>& prices) {
int last = 0, profit = 0;
for (int i = 0; i < (int)prices.size() - 1; ++i) {
last = max(0, last + prices[i+1] - prices[i]);
profit = max(profit, last);
}
return profit;
}
作者：ivan_allen
链接：https://leetcode-cn.com/problems/two-sum/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
