题目描述
买卖股票的最佳时机
给定一个数组 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

题解
分析：
这道题目，最开始暴力求解会发现超时，其实对暴力解法简单处理一下就可以拿下这道题目了。

• 在我们暴力求解的时候，其实当我们从第$prices[i=0]$开始计算其与$prices[i>0]$的最大差max之后，再计算$prices[i](i=1)$与$prices[j](j>i)$之间的最大差的时候，如果$prices[i](i=1)$的值大于或等于$prices[i=0]$的值，那么它与$prices[i>1]$的最大差肯定要小于或等于max，因此此时就不需要计算了。
• 否则再循环计算$prices[i]与prices[j](j>i)$的最大差，然后与max进行比较并更新，并记录下prices[i]，这样后面的prices[j]只有比prices[i]小，获得的利益才有可能比prices[i]获得的利益大。

int maxProfit(int* prices, int pricesSize){int max = 0;int temp = prices[0];for(int i = 0; i < pricesSize - 1; i++){if(i >= 1 && prices[i] >= temp){continue;}else{temp = prices[i];for(int j = i+1; j < pricesSize; j++){max = fmax(max, prices[j] - prices[i]);}}}return max;
}

这样的话，时间复杂度就比$O(N^2)$小，但是当prices是个递减数列时，最坏时间复杂度仍然是$O(N^2)$。

进一步改进：

• 其实有了上面的理解之后，很轻松的可以理解在线处理这种方式：购买股票获取的利益其实就是从买入的那天开始，后面的每一天的涨跌情况的累计，购入后一旦利益累计小于0，那么就令累计利益归0。在这个过程中去判断累计利益的最大值。

• 具体的，设置一个sum记录prices[i]与prices[i+1]之间的差值，然后逐步累加，一旦累计小于0就记为0，同时设置max作为最大利益，在累计时且每次比较获得max与sum的最大值。

• 最后返回max

• 其实可以看出来，在上面的设计过程中，获取的利益只于上一个状态获取的利益相关，这就是动态规划，其实我们也可以把这个动态规划方程表示出来：f(i)=f(i−1)+max{0,prices[i]−prices[i−1]}f(i) = f(i-1)+max\{ 0, prices[i] - prices[i-1] \}f(i)=f(i−1)+max{0,prices[i]−prices[i−1]}

int maxProfit(int* prices, int pricesSize){int sum = 0;int max = 0;for(int i = 0; i < pricesSize - 1; i++){sum += prices[i+1] - prices[i];max = fmax(sum, max);if(sum < 0){sum = 0;}}return max;
}

---

关于在线处理，在求解最大子序和的时候也用到过。在线处理其实就是动态规划，当前状态只于上一个状态有关。