《LeetCode》—— 买卖股票的最佳时机_买卖股票的最佳时机leecode

本期，我将给大家讲解的是有关动态规划类的题——买卖股票的最佳时机。这个系列总共有四道题。接下来，让我们一起去看看！！！

---

目录

（一）买卖股票的最佳时机

（二）买卖股票的最佳时机 II

（三）买卖股票的最佳时机 III

（四）买卖股票的最佳时机 IV

---

（一）买卖股票的最佳时机

LeetCode题目链接：买卖股票的最佳时机

题目如下：

 

题目分析：

第一题，我们先来看最简单的（题目的难度也是逐级提升的）。

• 思路一：

首先，我们有的小伙伴一读题，最先想到的可能就是暴力去求解这道题目，但是很遗憾当我们提交代码的时候显示的是代码超时了。因此，很显然暴力解法显然不是出题者要考察我们的地方。

• 思路二：

那么暴力求解不行，还有没有其他思路呢？我们通过分析题目，主要意思就是找到最多一次买卖股票可以获得的最大利润的问题的解决方案。我们可以利用贪心的思路来分析，主要原理是跟踪到目前为止看到的最低价格和以当前价格卖出可以获得的最大利润，通过迭代价格并相应地更新这些值，我们可以找到可以获得的最大利润。

• 思路三：

那么除了上述的贪心去求解还有没有其他思路呢？其实还有一种我们今天主要讲的动态规划算法。

解题思路：

在这里，我只给出动态规划的具体实现过程。

• step1：确定【arry】数组以及下标的含义

首先，我们初始化一个二维数组 arry，其中大小是价格向量的大小（size为给出的数组 prices 的大小），arry 中每行的第一个元素表示买入或者卖出的天数，第二个元素表示当天的状态。

arry[i][0]：

• 表示第i天持有股票所得最多现金 。因为刚开始时没钱买，所以开始现金是0，因此第i天买入股票现金就是 -prices[i]， 这是一个负数；
• arry[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以arry[0][0] -= prices[0];

arry[i][1]：

• 表示第i天不持有股票所得最多现金，即也许是一直都还没有没有买入，或者要卖出；
• arry[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以arry[0][1] = 0;

---

• step2：确定递推公式

如果第i天持有股票即arry[i][0]， 那么递归公式可以像如下这样：

• 如果在当前前的前一天即（ i-1） 天就持有股票的话，那么当前所持有的现金就是昨天持有股票的所得现金 即：arry[i - 1][0]
• 如果是在当前这一天买入股票即（i），那么此时所持有的就是买入今天的股票后所得现金即：-prices[i]（为负数）