题目链接：Best Time to Buy and Sell Stock

Say you have an array for which the i-th 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.

这道题的要求是用数组中的数字表示股票的价格，然后最多只允许1次买入卖出，计算最大利益。

通俗地理解，只需要在最低的时候买入，最高的时候卖出即可。因此采用变量low记录股票最低价格，由于卖出是在买入后才能进行的，因此每次low与前一天的股票价格（即prices[i-1]）比较取较小的。接下来用当前股票价格减去low即可得到当前利益，然后找出最大值即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int res = 0, low = INT_MAX;
        for(int i = 1; i < prices.size(); ++ i)
        {
            low = min(low, prices[i - 1]);
            res = max(res, prices[i] - low);
        }
        return res;
    }
};

当然，也可以采用动态规划的思路，用cur表示当天卖出时的最大利益，用res表示全局的最大利益。因此递推公式是：

  • cur = max(0, cur+prices[i]-prices[i-1])；
  • res = max(res, cur)。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int res = 0, cur = 0;
        for(int i = 1; i < prices.size(); ++ i)
        {
            cur = max(0, cur + prices[i] - prices[i - 1]);
            res = max(res, cur);
        }
        return res;
    }
};