如何买卖股票？不要慌，我有妙招！

╰+攻爆jí腚メ 2022-03-15 10:33 182阅读 0赞

预计阅读时间15分钟。

Leetcode第121题到123题连续出现了三道买卖股票相关的题目，一年前的网易笔试和半年前的百度面试都遇到过121题，不过不用慌，看完本文，你一定能够完美解决买卖股票的问题。那么我们由易到难，依次介绍这三道题目。

# **121. Best Time to Buy and Sell Stock** #

121题题目是这样的：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

在所有的过程中，我们只允许一次的买卖，基于这个问题，我们得到了下面的两种解法。

**解法1**

根据题意，我们只需要找出数组中最大的差值即可，即 max(prices\[j\] – prices\[i\]) ，i < j。

如何得到最大的差值，只需要一次遍历即可，在遍历的用一个变量记录遍历到当前时的最小值即可。时间复杂度为O(n).

相关的实现代码如下：

class Solution {
        
    public int maxProfit(int[] prices) {
        
    if (prices == null || prices.length < 2) {
        
        return 0;
    }
    
    int min = prices[0];
    int profit = 0;
    
    // 第i天的价格可以看作是买入价也可以看作是卖出价
    for (int i = 1; i < prices.length; i++) {
        
        // 找到更低的买入价
        if (min > prices[i]) {
        
            // 更新买入价
            min = prices[I];
        } 
        // 当天的价格不低于买入价
        else {
        
            // 如果当天买出的价格比之前卖出的价格高
            if (profit < prices[i] - min) {
        
                // 更新卖出价
                profit = prices[i] - min;
            } 
        }
    }
    
    return profit;
      }
    }

**解法2**

第二题的解法是我在面试百度的时候想到的，应用的是求数组中和最大的连续子数组序列的思路，这种思路又被称为Kadane's Algorithm。我们有两个问题：

如何转化为求数组中的和最大的连续子序列？相邻两个数作差即可，这样的话子序列的和就是我们在子序列开始卖出股票，在子序列最后买回股票所能得到的收益。

那么什么是Kadane's Algorithm呢？

kadane算法利用了数学归纳法的思想。简单来讲就是，随意给你一个现成的数组，比如说−2, 1, −3, 4, −1, 2, 1, −5, 4，让你求其中的最大子列和，并不是容易的事情。但如果我们能从第一个数开始，随着数组的扩充，始终对其最大子列和保持跟踪，就可以轻易的求出任意一个数组的最大子列和。换言之，长度n的数组我们不会求，长度为一的总能算出来吧？长度为一的算出来了，二也就能算出来，二算出来了，三就能算出来，以此类推，用这种根据i求i+1的思想，我们就能达到最终目的。

详细的分析一下，往一个长度为i的数组后面插入第i+1个数，这时，数组的最大子列只有两种情况，要么包括第i+1个数，要么不包括第i+1个数。即：

maxsubarraum = max(以第i+1个数结尾的子列和， 不以第i+1个数结尾的子列和)。\*

先计算前者，以第i+1个数结尾的子列和怎么算呢？很简单，要么它是以第i个数结尾的子列作为前缀，要么它不以之作为前缀。假设第i+1个数为x，那么：

以第i+1个数结尾的子列和 = max(x，以第i个数结尾的子列和+x) (1)。

再计算后者，也就是不以第i+1个数结尾的子列和。这啥意思呢？其实就是插入第i+1个数之前的数组的最大子列和嘛。我们的数学归纳思想也就体现在这里，如果你还看不明白，我们将\*式改写：

数列长度i+1的最大子列和 = max(以第i+1个数结尾的子列和， 数列长度i的最大子列和)。(2)

看到了吧，无论(1)式还是(2)式，后一种情况都可以由前一种情况推出，妥妥的数学归纳。我们的算法只要从i=1开始，一步一步按照上面的规则走下去，那么任意一个数列的最大子列和就能求出来了！

class Solution {
        
    public int maxProfit(int[] prices) {
        
    if(prices==null || prices.length<2)
        return 0;
    int maxCur = 0;
    int maxSoFar = 0;
    for(int i=1;i<prices.length;i++){
        
        maxCur = Math.max(0,Math.max(prices[i]-prices[i-1],maxCur + prices[i] - prices[i-1]));
        maxSoFar = Math.max(maxCur,maxSoFar);
    }
    return maxSoFar;
      }
    }

# **122. Best Time to Buy and Sell Stock II** #

这道题的描述如下：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

这道题允许无限次的买卖，简直太简单了吧，只要后一天的价值比前一天的大，那就买卖呗。不忍吐槽的一道题，代码如下：

class Solution {
        
    public int maxProfit(int[] prices) {
        
    if(prices==null || prices.length<2)
        return 0;
    int maxProf = 0;
    for(int i = 1;i<prices.length;i++){
        
        maxProf += (prices[i] > prices[i-1] ? prices[i] - prices[i-1]:0);
    }
    return maxProf;
      }
    }

# 123. Best Time to Buy and Sell Stock III #

这一题还是比较难的，题目描述如下：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

我们只允许最多两次的买卖，这可如何是好？我们同样提供两种思路：

**解法1**

这个问题可以转换成Best Time to Buy and Sell Stock I问题。

两次股票交易的核心是可以定义一个交易点，在这个交易点之前可以做一次交易(赚的最大数目的钱为firstProf)，在这个交易点之后可以做一个交易(赚的最大数目的钱是secondProf)。那么要求的是max(firstProf+secondProf)。但是这个方法的时间复杂度是O(N^2)，空间复杂度是O(1)。leetcode中显示超时。

可以使用两次扫描的方法避免上面的双重循环。

不同于Best Time to Buy and Sell Stock I中定义的初始状态A\[i\]表示第i天卖出挣的最大数目的钱，这个更进一步直接定义A\[i\]表示前i天赚的最大数目的钱。minPrice表示从第0天到第i-1天中的最低价格。

A\[0\]=0。（初始状态）  
A\[1\]=max(prices\[1\]-prices\[0\],A\[0\])  
A\[2\]=max(prices\[2\]-minPrice,A\[1\])  
.....

即A\[i\]=max(price\[i\]-minPrice,A\[i-1\]).

另外一次扫描从数组后向前扫描，定义B\[i\]表示从第i天到最后一天n能赚的最大数目的钱。maxPrice表示第i+1天到n天的最高价格。  
B\[n\]=0。（初始状态）  
B\[n-1\]=max(maxPrice-prices\[n-1\],B\[n\])  
B\[n-2\]=max(maxPrice-prices\[n-2\],B\[n-1\])  
.....

即B\[i\]=max(maxPrice-prices\[i\],B\[i+1\])

那么以第i天为分割点能赚的最多数目的钱为A\[i\]+B\[i\]  
问题的解为max\{A\[i\]+B\[i\]\}。0<=i<=n。  
时间复杂度是O(N)，空间复杂度是O(N)。

**解法2**

第二种解法的核心是假设手上最开始只有0元钱，那么如果买入股票的价格为price，手上的钱需要减去这个price，如果卖出股票的价格为price，手上的钱需要加上这个price。

因此我们定义了4个状态：

Buy1\[i\]表示前i天做第一笔交易买入股票后剩下的最多的钱；  
Sell1\[i\]表示前i天做第一笔交易卖出股票后剩下的最多的钱；  
Buy2\[i\]表示前i天做第二笔交易买入股票后剩下的最多的钱；  
Sell2\[i\]表示前i天做第二笔交易卖出股票后剩下的最多的钱；

那么假设我们在第i天时第二次卖出股票，我们卖出股票可以获得Buy2\[i-1\]+prices\[i\]的钱，假设在第i天前已经完成了两笔交易，那么我们最多的钱是Sell2\[i-1\]，因此  
Sell2\[i\]=max\{Sell2\[i-1\],Buy2\[i-1\]+prices\[I\]\}

同样的道理，假设我们在第i天时第二次买入股票，我们手中的钱是Sell\[i-1\]-prices\[i\]，假设我们在第i天钱已经卖出了两次股票，那么我们最多的钱是Buy2\[i-1\]，因此  
Buy2\[i\]=max\{Buy2\[i-1\],Sell\[i-1\]-prices\[I\]\}

同样的道理我们还可以得到：  
Sell1\[i\]=max\{Sell\[i-1\],Buy1\[i-1\]+prices\[I\]\}  
Buy1\[i\]=max\{Buy\[i-1\],-prices\[I\]\}

可以发现上面四个状态都是只与前一个状态有关，所以可以不使用数组而是使用变量来存储即可。

这是leetcode中的讨论网址：https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1

# **参考文献** #

1、从一道easy leetcode问题，谈谈最大子列和的Kadane算法：http://blog.csdn.net/The\_\_Apollo/article/details/77367534

2、LeetCode123:Best Time to Buy and Sell Stock III：http://blog.csdn.net/u012501459/article/details/46514309

原文链接：https://mp.weixin.qq.com/s?\_\_biz=MzI1MzY0MzE4Mg==&mid=2247483854&idx=1&sn=1e02111e01e0c5aac1e0bc9027b4c990&chksm=e9d0110fdea798192f80cb6ab6a6c7bcb1f17e5cbe48172e95945ea2744c1059af67d1129d9c&scene=21\#wechat\_redirect

> 查阅更为简洁方便的分类文章以及最新的课程、产品信息，请移步至全新呈现的“LeadAI学院官网”：
> 
> www.leadai.org

请关注人工智能LeadAI公众号，查看更多专业文章

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

大家都在看

![640.png?][640.png]

[LSTM模型在问答系统中的应用][LSTM]

[基于TensorFlow的神经网络解决用户流失概览问题][TensorFlow]

[最全常见算法工程师面试题目整理（一）][Link 1]

[最全常见算法工程师面试题目整理（二）][Link 2]

[TensorFlow从1到2 | 第三章 深度学习革命的开端：卷积神经网络][TensorFlow_1_2 _ _]

[装饰器 | Python高级编程][_ Python]

[今天不如来复习下Python基础][Python]

[640_wx_fmt_jpeg]: /images/20220315/d418f365a0ec4ac198b6cee9a4c6d007.png
[640_wx_fmt_jpeg 1]: /images/20220315/98e46501681d4a9cb4648b652e4650b0.png
[640_wx_fmt_jpeg 2]: /images/20220315/bb4efbbfc79c48569402b3bdc95aa0cd.png
[640_wx_fmt_jpeg 3]: /images/20220315/7554fe4e473b4f0c982230337282d84d.png
[640.png]: /images/20220315/2c01a83ab38849389e2f5720e0d2fb6a.png
[LSTM]: http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484578&idx=3&sn=38654576f40c7c086fbe32d2b12c9862&chksm=eadbad7fddac246979cf49802a01c3136b1b0f79e6bfb3e9ace2172cfff4ed63be89f23b0f64&scene=21#wechat_redirect
[TensorFlow]: http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484570&idx=4&sn=d22e41ff43460c040aae136b78f5c807&chksm=eadbad47ddac2451057b1c6975191f1044988fe9612e1fc248852fe2490052dd791c42770d96&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484530&idx=1&sn=462931eb9fd0dd1ac41f2e3f987fa51c&chksm=eadbadafddac24b91389d1bcea23be2668a0efbd425150e836d1ee5ba6d182b0a2f3cf6000dc&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484551&idx=3&sn=a481218ee3f5f4d766a48dca5f8c4c61&chksm=eadbad5addac244c9a9516376add6168ff1a415ba26994ede28c1613dfcc54222959c56a365f&scene=21#wechat_redirect
[TensorFlow_1_2 _ _]: http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484516&idx=1&sn=40e8928353dbc29f17c8e22cd27944f4&chksm=eadbadb9ddac24af5943085537922db2f982f088f34ce20262eea314dbf5741dcefbc4a74404&scene=21#wechat_redirect
[_ Python]: http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484476&idx=1&sn=503166979eeff5c974de3e3ce0d4b12e&chksm=eadbade1ddac24f70b22b22cb81a070fdab2e4dafc02c596eb3aa5acba83a9d1051e122258e2&scene=21#wechat_redirect
[Python]: http://mp.weixin.qq.com/s?__biz=MzI2OTc5NTUwNg==&mid=2247484452&idx=1&sn=c1cf5f55330a5ef89f0bce7faeda4c98&chksm=eadbadf9ddac24ef6e87ee35cc017d42a9ade6e47522b8a041a4b01227161bb17ce6102eafe0&scene=21#wechat_redirect