买卖股票的最佳一次交易

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

---

如果你不知道最大子数组问题，或者知道但是看不出来和这道题有什么关系（比如我），那么这个问题就比较难解。

笨思路闲谈（可跳过）：首先，我们可能考虑直接求最大最小值，但是问题是，股票交易有时间先后，那么如果最大值出现在最小值之前就是无效的。考虑到股票要低入高出，那么解法可能是：首先从前找到上升的时间点a，因为我们希望股票涨，从后找到下降的时间点b，因为我们希望卖出后才跌，那么就可以找到两个候选点，那么最优情况出现在[a,b]或(a,b])或[a,b)，然后对后面两个自问题求解，比较三者就可以得出结论，但是问题是，时间会超出，虽然是启发式寻找解，依旧没有下面的方法快。

利用最大子数组问题求解：

public int maxProfit(int[] prices) {
    int maxCur = 0, maxSoFar = 0;
    for(int i = 1; i < prices.length; i++) {
        maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
        maxSoFar = Math.max(maxCur, maxSoFar);
    }
    return maxSoFar;
}

最大子数组问题是找到和最大的子数组，和这个好像不是很一致，我们思路转变下，把股票的绝对量转为相对量，加入数据是差值，比如今天比昨天相比的增加或减少的量，那么求和就是我们成交的收益，这样问题就一致了，代码中求和的也是差值。