股票买卖问题在LeetCode上有三个分问，可见LeetCode对这道题的喜爱。这道题也确实不错，考察了动态规划，又和实际结合在了一起。

我在面试的时候曾经被问到这道题的第一问，我虽然解出来了，但是使用的动态转移方程并不是面试官想要的。
当时我的自我感觉还不错，没想到的是其实这问题后面还有两个更难的扩展。。。

股票买卖问题1
股票买卖问题2
股票买卖问题3

股票买卖问题说的是给定一组股票价格的序列（按时间），问你如何买卖可以达到利润的最大化。

股票买卖问题1

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.

假设你只能买卖一次股票，那你能达到的最大利润是多少？

这里可以以某个时间点的股票价格为观察点，如果要在这个时间点卖出股票，那能获得的最大利润是这个时间点之前的最高股票价格和这个时间点的股票价格差值。
所以我们只要对于每个时间点都知道它之前的股票最低价格就可以了。

int maxProfit(vector<int>& prices)
{
    int len = prices.size();
    if (len <= 1)
        return 0;
    int min = prices[0];
    int max = 0;
    for (int i = 1; i < len; i++)
    {
        if (prices[i] > min)
        {
            if (prices[i] - min > max)
                max = prices[i] - min;
        }
        else if (prices[i] < min)
            min = prices[i];
    }
    return max;
}

股票买卖问题2

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

现在假设你可以无限次售卖股票，不过不能同时持有两支股票，问你能获得的最大利润是多少。
这里看起来很复杂，因为从一次售卖，变成了多次售卖，计算好像复杂很多。
但是观察股票价格的序列图，我们可以发现一个规律。

假设在i时间点我们可以获利p，如果i + 1时间点的股票价格比i时间点的价格高m，那i + 1时间点能获得的利润就是p + m。
这里我们可以考虑i时间点股票价格的两种情况

• 这里卖出了股票，那就可以改成在i + 1时间点卖出股票，因为
  i + 1时间点股票价格更高。

• 这里没有卖出股票，说明这里的股票价格比前面一个卖出股票点低（如果有卖出点的话），那这i时间点就是股票价格最低点，那选择在这里买股票，i + 1卖股票也可以获得最大利润。

综上所述，i＋１点股票价格比ｉ点高时，ｉ＋１点能获得的最大利润比ｉ点高了他们之间的股票差价。如果ｉ＋１点股票价格比ｉ点低，那ｉ＋１点获得的利润和ｉ点一样。

int maxProfit(vector<int>& prices)
{
    int len = prices.size();
    if (len <= 1)
        return 0;
    int max = 0;
    for (int i = 1; i < len; i++)
    {
        if (prices[i] > prices[i - 1])
            max += prices[i] - prices[i - 1];
    }
    return max;
}

股票买卖问题3

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

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

这题就比上面两题复杂很多了，现在我乍一看也没有很好的办法。。。
交易的次数被限制到了两次，不是一次，也不是无限次。
两次的交易就很麻烦了，看来得动态规划，保存中间信息来计算最后的结果。

首先计算一次交易的情况下在每个时间点我们能获得的最大利润。这个和第一题一样，可以轻松动态规划完成，只要保存之前的股票最低价格就可以了。

然后我们反向遍历股票价格序列，寻找某个时间点之后的最大股票价格，这样，我们就能知道在某个时间点购入股票的话能够获取的最大利润是多少。

然后将上述两种信息合并在一起，我们就能知道在某个时间点之前卖一次股票，并在这个时间点购入股票后的总收益是多少。

int maxProfit(vector<int> &prices)
{
    int len = prices.size();
    if (len <= 1)
        return 0;
    vector<int> one_max(len);
    int max = 0;
    one_max[0] = 0;
    int min = prices[0];
    for (int i = 1; i < len; i++)
    {
        if (prices[i] <= prices[i - 1])
        {
            one_max[i] = one_max[i - 1];
            min = min > prices[i] ? prices[i] : min;
        }
        else
        {
            one_max[i] = prices[i] - min > one_max[i - 1] ?
                prices[i] - min : one_max[i - 1];
        }
    }
    vector<int> max2(len);
    max2[len - 1] = prices[len - 1];
    for (int i = len - 2; i >= 2; i--)
    {
        max2[i] = max2[i + 1];
        if (prices[i] > max2[i])
            max2[i] = prices[i];
    }
    int two_max = 0;
    for (int i = 1; i < len - 1; i++)
    {
        if (one_max[i] + max2[i + 1] - prices[i + 1] > two_max)
            two_max = one_max[i] + max2[i + 1] - prices[i + 1];
    }
    if (two_max > one_max[len - 1])
        max = two_max;
    else
        max = one_max[len - 1];
    return max;
}