121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路：

利用贪心的思想，首先分析从0到i的区间的最大利润，分几种情况，在i之前买和卖了，在i之前买了但没卖，在i之前没买也没卖。故可以得知买和卖的情况是随着数组数字的不断进入而动态变换的，因此可以设一个变量a表示当前最小的数，b为a之后出现的最大的数（注意b一定是出现在a的后面的，因为必须先买才能卖），那么做法就很简单了，每当遇到比a小的数就更新a，遇到比b大的数就更新b，更新完b以后b-a就是可能的最大利益。那么该如何保证b在a的后面呢，就是每当a更新完后就使得b=a，这样除非后面遇到更大的数，否则b的值不变，就不会更新利益结果，这样就保证了b一定是在a的后面。然后，对于无法获得利润返回0的情况，处理起来也很简单，利润返回零只有可能是数组是从大到小排列的，那么b的值将永远不会更新，只需要初始时让长度为0，不更新就正常返回零即可。

class Solution {
public:int maxProfit(vector<int>& prices) {int a=prices[0],b=-1;int len=-1;for(auto e:prices){if(a>e){a=e;b=-1;}if(b<e){b=e;len=max(len,b-a);}}return len;}
};