题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

1
2
3
4

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

1
2
3

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题解

这道题依旧是动态规划。虽然之前看过关于这道题的文章，但是也有一些印象，但这次自己想了好久依旧没有想出来，最后还是看了解析。

准确来说，还是要搞清楚状态，在这道题中共有两个状态，一个是天，另外一个是是否持有股票。最开始自己根据印象，知道有买入、卖出、不动这三种情况，但自己误以为这是3种状态，加上天数，共有4种状态，这个实际上是错了，买入、卖出、不动这3个实际上一种状态，类似于1天、2天、3天这种类型。

这样就只有2种状态，可以用存储一个二维的数组存储状态数据，至于数组中的值，肯定是当前状态所属的收益了。接下来开始思考状态转移方程。

我们每天有3种选择，分别是，

  1. 买入，这样当天的收益是负的买入价。
  2. 不动，这个时候收益与之前不变。
  3. 卖出，这个时候的收益是当前价减去之前的收益。

求最大收益，那么就是上面这3种情况的最大值，由于不动并不改变收益，因此我们实际可以将其省去。

这里想了半天，虽然昨天看了解答，但自己依旧想不起来，今天又看了一下，由于状态有2个，因此方程是有2个的，而不是只有1个方程，自己一直陷入到了只有1个方程的局限中。

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

// 买入为0，卖出为1
// 看了解析，这里实际不太好理解，应该是持有的话为1，不持有为0，这样更容易理解，而买入、卖出是行为，行为用状态比较难描述，而且还有一个平仓的行为，更加难解释
买入： f(i, 0) = -price[i];
卖出： f(i, 1) = price[i] + f(i - 1, 0)

// 改为下面这样子
持有：f(i, 1) = -price[i];
不持有: f(i, 0) = price[i] + f(i - 1, 0)

// 如果持有，那么收益有两种情况，
// 昨天就持有，收益为昨天的收益
// 今天才持有，那么收益为今天的收益，收益为负的
f(i, 1) = max{ -price[i], f(i - 1, 1) }
// 如果不持有，有两种情况，
// 昨天就不持有，那么收益为昨天卖出后的收益
// 今天开始卖，那么收益为今天的价格减去昨天的收益（负的）
f(i, 0) = max{ f(i - 1, 0), f(i - 1, 1) + price[i] }

有了状态转移方程，我们再想下基准态，即第0天，我们不持有，那么收益为0，如果持有，那么收益显然为负的。

最后，我们想要的结果是f(N, 0)，即如果总共有N天，那么我们需要获取在第N天不持有股票的值，持有的话，肯定是赔钱的。

接下来尝试根据上面的状态转移方程写程序。实现如下：

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

int maxProfit(vector<int>& prices) {
   if (prices.empty()) return 0;

   int (*dp)[2] = new int[prices.size()][2];
   dp[0][0] = 0;
   dp[0][1] = -prices[0];
   
   for (int i = 1; i < prices.size(); i++) {
       dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
       dp[i][1] = max(-prices[i], dp[i - 1][1]);
   }

   return dp[prices.size() - 1][0];
}

上面的方式中，可以发现状态转移方程中只使用了前一天的数据， 因此可以只使用2个变量存储起来，使得空间效率为O(1)，实现如下。

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

int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;

    int a = 0;
    int b = -prices[0];
    for (int i = 1; i < prices.size(); i++) {
        a = max(a, b + prices[i]);
        b = max(-prices[i], b);
    }

    return a;
}

优化后的程序时间复杂度为O(N)，空间复杂度为O(1)。

自己对于这道题的最初想法是双层循环遍历，那样的话，算法复杂度差不多为O(N ^ 2)，使用动态规划优化了很多。

最后来看，整个过程感觉有点像二叉树，但又不像，需要再想想。

另外还有个问题，题目要求只能够交易一次，似乎实现中并未专门考虑这个条件，但仔细一想，会发现这个条件暗含在了状态转移方程中。

如果我们不持有，那么结果要么是依旧不持有，要么是已经卖了；如果我们持有，那么我们要么本来就持有，那么就是现在持有。如果是多次交易，肯定有从非持有到持有这个状态的转换，但从状态转移方程中并没有这个情况的体现。因此不会发生这个情况。虽然状态转移方程中有一开始的持有操作，但这个操作整体来看只有1次，不会有多次，因此可以认为是无影响的。