AI支招！终于知道如何买卖股票了！ 妙招，干货

很多朋友对AI支招！终于知道如何买卖股票了！，妙招，干货不是很了解，每日小编刚好整理了这方面的知识，今天就来带大家一探究竟。

Leetcode第121题到第123题有连续三道与买卖股票相关的问题。一年前的网易笔试和半年前的百度面试都遇到过121题。但不要惊慌。看完这篇文章，你一定能够完美解决。关于买卖股票的问题。接下来我们就按照从易到难的顺序来介绍这三个问题。

买卖股票的最佳时机

第121题如下：

在所有流程中，我们只允许一次购买和销售。基于这个问题，我们得到了以下两种解决方案。

解法一根据题意，我们只需要找到数组中最大的差值，即max(prices[j] prices[i]) , i j 。

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

相关实现代码如下：

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length2){return0;}intmin=prices[0];intprofit=0;//可视为第i天的价格作为买入价也可以视为卖出价for(inti=1;iprices[i]){//更新买入价min=prices[I];}//当日价格不低于the买入价else{//如果当天的买入价高于之前的卖出价if（盈利），第二个问题的解决方案是我在百度面试时提出的。它利用了寻找数组中最大的连续子数组序列的思想。这个想法也被称为卡丹算法。我们有两个问题：

如何转化为求数组中和最大的连续子序列呢？只需计算两个相邻数字之间的差异即可。在这种情况下，子序列的总和就是我们在子序列开始时卖出股票并在子序列结束时买回股票可以获得的利润。

那么什么是Kadane算法呢？

Kadane算法利用了数学归纳法的思想。简单来说，随机给你一个现成的数组，比如2, 1, 3, 4, 1, 2, 1, 5, 4，让你找出其中最大子列总和。事物。但是，如果我们可以从第一个数字开始，并随着数组扩展跟踪其最大子列和，我们就可以轻松找到任何数组的最大子列和。换句话说，我们不会找到长度为n的数组，但我们总能计算出长度为1的数组，对吗？一旦计算出一个的长度，就可以计算出两个，再计算出两个，再计算出三个，以此类推。利用这种根据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开始，一步步遵循上面的规则，就可以找到任意序列的最大子序列和！

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length2)return0;intmaxCur=0;intmaxSoFar=0;for(inti=1;i) 本题描述如下：

此问题允许无限购买和出售。实在是太简单了。只要第二天的价值大于前一天，那么就可以买卖。一个我不忍心吐槽的问题，代码如下：

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length2)return0;intmaxProf=0;for(inti=1;iprices[i-1]?prices[i]-prices[i- 1]:0);}returnmaxProf;}}123 买卖股票的最佳时机III 这题比较难。问题描述如下：

我们最多只允许两次交易，我们该怎么办？我们还提供两个想法：

解1 这个问题可以转化为买卖股票的最佳时机I 问题。

两股交易的核心是可以定义一个交易点。在该交易点之前，可以进行交易（最高赚取的金额为firstProf），在该交易点之后，可以进行交易（最高赚取的金额为firstProf）。第二教授）。那么需要的是max(firstProf+secondProf)。但该方法的时间复杂度为O(N^2)，空间复杂度为O(1)。 leetcode 中显示超时。

可以使用两次扫描来避免上述双循环。

与最佳买卖股票时机一中定义的初始状态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]表示n从第i天到最后一天能赚到的最大金额。

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)。

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length2)return0;int[]asc=newint[prices.length];int[]desc=newint[prices.length];intn=prices.length;intminprice=prices[0];intmaxProf=0;asc[0]=0;for(inti=1;i=0;i--){desc[i]=Math.max(maxprice-prices[ i],maxProf);maxprice=Math.max(maxprice,prices[i]);maxProf=desc[i];}maxProf=0;for(inti=0;i第二个解法的核心是假设最一开始只有0元，那么如果买入股票的价格是价格，则需要在这个价格中减去手上的钱，如果卖出股票的价格是价格，则需要加上手上的钱到这个价格。

因此我们定义了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]-价格[I]}同理，我们也可以得到： Sell1[i]=max{Sell[i-1],Buy1[ i-1]+prices[I]}Buy1[i]=max{Buy[ i-1],-价格[I]}

可以发现，以上四种状态只与前一个状态相关，因此可以使用变量而不是数组来存储。

以上知识分享希望能够帮助到大家！