# 买卖股票的最佳时机——数组、动态规划

> 发布于：2022-03-09 | 分类：刷题 | 原文：https://www.imbailey.cn/post/leetcode-121-best-time-to-buy-and-sell-stock

## 题目

> 本题目来自：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

#### 121. 买卖股票的最佳时机

难度简单2177收藏分享切换为英文接收动态反馈

给定一个数组 `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 <= 105`
- `0 <= prices[i] <= 104`

## 题解

### 暴力法

超时，不必多说。

```c++
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max = 0;
        for( int i=0;i<prices.size()-2;i++){
            for(int j=i+1;j<prices.size()-1;j++){
                if(prices[j]-prices[i]>max){
                    max = prices[j]-prices[i];
                }
            }
        }
        return max;
    }
};
```

时间复杂度O(n^2)，空间复杂度O(1)

### 动态规划

假设我们有穿越时空的能力，再假设我们决定在第`i`天卖出，那么只要知道在`0~i`天的最低价，再穿越回去购买股票，就能获得最大收益了。

创建一个`dp[i]`数组，表示在第`i`天卖出时的最低价。

然后再根据`dp[i]`数组，找到收益最大的那一天，即确定`prices[i]-dp[i]`的最大值。

```c++
//dp[i]表示截止到i，价格的最低点是多少   dp[i]=min(dp[i-1],nums[i])
int max = 0;
int[] dp = new int[prices.length];
dp[0] = prices[0];
for (int i = 1; i < prices.length; i++) {
  dp[i] = (dp[i - 1] < prices[i]) ? dp[i - 1] : prices[i];
  max = (prices[i] - dp[i]) > max ? prices[i] - dp[i] : max;
}
return max;

// 参考https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/930057
```

这个代码还可以进一步优化，因为我们只关注最大值，所以可以不用把所有数据都存到数组里。维护一个`minprice`和`maxprofit`变量即可。

```c++
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for(int price:prices){
            minprice = min(price, minprice);
            maxprofit = max(maxprofit, price-minprice);
        }
        return maxprofit;
    }
};
```

这样只要遍历一遍数组，时间复杂度O(n)，空间复杂度O(1)。

### 其他小问题

1e9表示1*10^9。在算法题中常用来赋一个非常大的值。为什么不用1e10呢？因为int类型中1e10会溢出。

详情可以参考：http://t.csdn.cn/rItZr