买卖股票的最佳时机-121

给定一个数组 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 ≤ 10
• 0 ≤ prices[i] ≤ 10

思路

我们创建一个dp[]数组，里面的值代表：到目前为止，我的收益最大值。

以示例一的序列为例：

• 假设只有 1 天，则dp[0] = 0，即无法买入也无法卖出，收益为0；

• 假设有 2 天，则dp[1] = max( dp[0], nums[1]-nums[0] )，即卖或不卖：

  • 在第二天卖出：收益为nums[1] - nums[0]；
  • 在第二天不卖出：收益为dp[i-1]；
  • 在这两个里面选一个最大的。

• 假设有 3 天，则dp[2] = max( dp[2-1], nums[2]-nums[0], nums[2]-nums[1] )，意思是：

  • 在第三天卖出，则可能得到：

    • val1 = nums[2] - nums[1]；
    • val2 = nums[2] - nums[0]；
  • 在第三天不卖出，则能得到val3 = dp[2-1]的收益；
  • 我们要在val1、val2、val3里选一个最大的。

• ….

• 如果有 i 天，则： %20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20dp(i-1)%2C%5C%20max%5C%7B%20nums%5Bi%5D-nums%5Bj%5D%20%5C%7D%5C%20%5C%7D%2C%20%26i%20%5Cge%201%20%E4%B8%94%200%20%5Cle%20j%20%5Clt%20i%0A%5Cend%7Bcases%7D%0A#card=math&code=dp%28i%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20dp%28i-1%29%2C%5C%20max%5C%7B%20nums%5Bi%5D-nums%5Bj%5D%20%5C%7D%5C%20%5C%7D%2C%20%26i%20%5Cge%201%20%E4%B8%94%200%20%5Cle%20j%20%5Clt%20i%0A%5Cend%7Bcases%7D%0A)

根据上面这个递推公式，写出下面的代码1，显而易见，这个代码是时间复杂度是 #card=math&code=O%28n%5E2%29)，这段代码只能通过199/210的测试用例。

仔细想想，其实我们只需要一次遍历就能求出dp[]的值。算法如下：

在进入循环前，先创建一个变量min_price = prices[0]，然后从prices[1]开始遍历：

%20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20dp(i-1)%2C%5C%20nums%5Bi%5D%20-%20min%5C_price%5C%20%5C%7D%2C%20%26i%20%5Cgt0%0A%5Cend%7Bcases%7D%0A#card=math&code=dp%28i%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20dp%28i-1%29%2C%5C%20nums%5Bi%5D%20-%20min%5C_price%5C%20%5C%7D%2C%20%26i%20%5Cgt0%0A%5Cend%7Bcases%7D%0A)

min_price记录到第 i 天为止的最小价格。到达第 i 天时，我们有两个选择：

• 卖：则收益是nums[i] - min_price；
• 不卖：则收益是dp[i-1]

AC代码在后面，其时间复杂度是 #card=math&code=O%28n%29)。

代码

第一次尝试：

class Solution {  // 199/210 超出时间限制
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1)   return 0;
        int* dp = new int[ prices.size() ];
        memset(dp, 0x0, sizeof(int) * prices.size());
        dp[0] = 0;
        for(int i = 1; i < prices.size(); i++) {
            for(int j = 0; j < i; j++) {
                int sell_it = prices[i] - prices[j];
                int no_sell = dp[i-1] > dp[i] ? dp[i-1] : dp[i];
                dp[i] = sell_it > no_sell ? sell_it : no_sell;
            }
        }
        int MAX = *max_element(dp, dp + prices.size());
        delete[] dp;
        return MAX;
    }
};

AC代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1)   return 0;
        int* dp = new int[ prices.size() ];
        memset(dp, 0x0, sizeof(int) * prices.size());
        dp[0] = 0;
        int min_price = prices[0];
        for(int i = 1; i < prices.size(); i++) {
            min_price = prices[i] < min_price ? prices[i] : min_price;
            int sell_it = prices[i] - min_price;
            int no_sell = dp[i-1];
            dp[i] = sell_it > no_sell ? sell_it : no_sell;
        }
        int MAX = *max_element(dp, dp + prices.size());
        delete[] dp;
        return MAX;
    }
};