难度中等307
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 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。限制：
0 <= 数组长度 <= 10^5注意：本题与主站 121 题相同：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
1、暴力解法
class Solution {
public:
int maxProfit(vector<int>& prices)
{
int ans = 0;
for (int i = 0; i < prices.size(); ++i)
{
for (int j = i + 1; j < prices.size(); ++j)
{
ans = max(ans, prices[j] - prices[i]);
}
}
return ans;
}
};
2、动态规划
仔细想一下！股票的最大利润，是不是就是某个最低谷和某个高峰的最大差值！并且还有一个细节，就是一个低谷之前可能存在其它低谷，它们之间是不会互相干扰的！
我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？
显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minprice = INT_MAX;
int maxprice = 0;
for(int i = 0; i < prices.size(); ++i)
{
// 获取每次差值price[i]-minprice和最大差值比较的最大值
maxprice = max(maxprice, prices[i] - minprice);
// 若峰值更低则更新
minprice = min(minprice, prices[i]);
}
return maxprice;
}
};