题目
给定一个数组 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。
题解
方法一：暴力求解
在这道题目中，我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。第一想法应该是最简单最容易写出的暴力算法：使用两个循环依次指向每个元素，使他们两两作差，得到的利益最大者被我们保存记录下来。看代码：
public class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit) {
maxprofit = profit;
}
}
}
return maxprofit;
}
}
代码很容易理解，技术含量不高，只需要弄清边界等细节即可。但是如此法操作必然会导致算法的性能较差，复杂度较高。所以我们还需要更为优秀的解法来解决这个问题。
方法二：双指针
不愧是双指针方法！又一次在数组题中大放异彩。那么究竟怎样使用双指针进行操作呢？直接从代码来学习这个方法：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxMoney = 0;//最大利润
int slowIndex = 0;//慢指针
int fastIndex = 1;//快指针
int lastIndex = prices.size() - 1;//最后索引
while(fastIndex <= lastIndex){
int money = prices[fastIndex] - prices[slowIndex];
if(money > maxMoney){
maxMoney = money;
}
if(money<0){
slowIndex = fastIndex;
}
fastIndex++;
}
return maxMoney;
}
};在这段代码中，我们首先定义了最大利润以及快慢两个指针，同时还根据数组大小取得了最后索引的值。下面进入一个循环，当快指针没有走到最后时，循环就反复执行。在循环中，我们首先去求得两指针对应数字间的差值，如果此差值大于最大利益，那么我们将最大利益更新为这次所做的差值。如果此差值为一个负数，那么就说明此时出现下降的趋势，不适合购入此股票，因此，我们将慢指针的移动到快指针的下方，跳过一些不必要的查找。不论money如何，我们的fast指针每一轮都会自增1，向前推进一步。最后直到指针越界，得到最大利益。
看完代码，我们还是有些云里雾里。这里给大家一个提示：解法一的暴力求解其实也是一种双指针，方法二只是一种更加聪明的优化版本。具体优化在哪里呢？方法一中，我们依次遍历每一个组合，做了很多不必要的尝试，但是在方法二中，我们能够在发现股票有下降至顶点趋势时，直接放弃慢指针所在的位置，加速跳跃到快指针所在位置继续查找，这样我们就可以迅速找到最低点，不需要摸着石头过河，而是戴上了一副望远镜。
总而言之，第二种方法其实是一种动态的变化，在遍历向前推进时，找到一个最小买入价格minprice，然后，在没有找到下一个更小的买入价格时，计算接下来每一天的利润，记录其中最大利润。如果找到下一个最小买入价格minprice，继续计算接下来未找到下一个更小买入价格时的利润最大值，直到遍历完prices数组，maxProfit就是历史最大差值。至此，方法二结束。
写在最后
对于这道题，其实还有更为优秀的动态规划解法，我希望多进行一些积累，在未来写一篇动态规划的合集，以专门一次性讲懂这系列问题。
