程序员算法实现-买卖股票的最佳时机系列问题

主要思路：因为只有一股可以交易，所以我们可以枚举 必须以i位置作为卖出时机的情况下，得到的最大收益是多少。如果我们得到每个i位置的最大收益，那么最大收益必是所有位置的最大收益的最大值 。

使用两个变量：

min变量：表示遍历到的位置之前的最小值是什么。

max变量：表示当前收集到必须以i位置卖出的最大收益是多少。

遍历数组一遍，在遍历到i位置的时候，min和max的更新逻辑如下：

遍历完数组，返回max的值就是最终答案。完整代码见：

主要思路：由于可以进行任意次的交易，但是任何时候最多只能持有一股股票，所以我们可以把股票曲线的所有 上升段 都抓取到，累加收益就是最大收益。遍历数组，遍历到的位置减去前一个位置的值，如果是正数，就收集，如果是负数，就把本次收益置为0（就等于没有做这次交易），这样遍历一遍数组，就不会错过所有的收益。

设置一个变量max，初始为0，用于收集最大收益值，来到i位置，max更新逻辑如下：

完整代码如下：

由本题可以简单得出一个结论： 如果数组元素个数为N，则最多执行N/2次交易就可以抓取所有的上升段的值（极端情况下，当前时刻买，下一个时刻卖，保持这样的交易一直到最后，执行的交易次数就是N/2） 。

主要思路：

在第2种情况下，我们定义

其中dp[i][j]表示[0...i]范围内交易j次获得的最大收益是多少。如果可以把dp这个二维表填好，那么返回dp[N-1][k]的值就是题目要的答案。

dp这个二维矩阵中，

第一行的值表示数组[0..0]范围内，交易若干次的最大收益，显然，都是0。

第一列的值表示数组[0...i]范围内，交易0次获得的最大收益，显然，也都是0。

针对任何一个普遍位置dp[i][j]的值，

我们可以枚举i位置是否参与交易，如果i位置不参与交易，那么dp[i][j] = dp[i-1][j]，如果i位置参与交易，那么i位置一定是最后一次的卖出时机。

那最后一次买入的时机，可以是如下情况：

最后一次买入的时机在i位置，那么dp[i][j] = dp[i][j-1] - arr[i] + arr[i]

最后一次买入的时机在i-1位置，那么dp[i][j] = dp[i-1][j-1] - arr[i-1] + arr[i]

最后一次买入的时机在i-2位置，那么dp[i][j] = dp[i-2][j-1] - arr[i-2] + arr[i]

...

最后一次买入的时机在0位置，那么dp[i][j] = dp[0][j-1] - arr[0] + arr[i]

完整代码如下：

上述代码中包含一个枚举行为

增加了时间复杂度，我们可以优化这个枚举。

我们可以举一个具体的例子来说明如何优化，

比如，

当我们求dp[5][3]这个值，我们可以枚举5位置是否参与交易，假设5位置不参与交易，那么dp[5][3] = dp[4][3]，假设5位置参与交易，那么5位置一定是最后一次的卖出时机。那最后一次买入的时机，可以是如下情况：

最后一次买入的时机在5位置，那么dp[5][3] = dp[5][2] - arr[5] + arr[5]

最后一次买入的时机在4位置，那么dp[5][3] = dp[4][2] - arr[4] + arr[5]

最后一次买入的时机在3位置，那么dp[5][3] = dp[3][2] - arr[3] + arr[5]

最后一次买入的时机在2位置，那么dp[5][3] = dp[2][2] - arr[2] + arr[5]

最后一次买入的时机在1位置，那么dp[5][3] = dp[1][2] - arr[1] + arr[5]

最后一次买入的时机在0位置，那么dp[5][3] = dp[0][2] - arr[0] + arr[5]

我们求dp[4][3]这个值，我们可以枚举4位置是否参与交易，假设4位置不参与交易，那么dp[4][3] = dp[3][3]，假设4位置参与交易，那么4位置一定是最后一次的卖出时机。那最后一次买入的时机，可以是如下情况：

最后一次买入的时机在4位置，那么dp[4][3] = dp[4][2] - arr[4] + arr[4]

最后一次买入的时机在3位置，那么dp[4][3] = dp[3][2] - arr[3] + arr[4]

最后一次买入的时机在2位置，那么dp[4][3] = dp[2][2] - arr[2] + arr[4]

最后一次买入的时机在1位置，那么dp[4][3] = dp[1][2] - arr[1] + arr[4]

最后一次买入的时机在0位置，那么dp[4][3] = dp[0][2] - arr[0] + arr[4]

比较dp[5][3]和dp[4][3]的依赖关系，可以得到如下结论：

假设在求dp[4][3]的过程中，以下递推式的最大值我们可以得到

dp[4][2] - arr[4]

dp[3][2] - arr[3]

dp[2][2] - arr[2]

dp[1][2] - arr[1]

dp[0][2] - arr[0]

我们把以上式子的最大值定义为best，那么

dp[5][3] = Math.max(dp[4][3],Math.max(dp[5][2] - arr[5] + arr[5], best + arr[5]))

所以dp[5][3]可以由dp[4][3]加速得到，

同理，

dp[4][3]可以通过dp[3][3]加速得到，

dp[3][3]可以通过dp[2][3]加速得到，

dp[2][3]可以通过dp[1][3]加速得到，

dp[1][3]可以很简单得出，dp[1][3]有如下几种可能性:

可能性1，1位置完全不参与，则

可能性2，1位置作为最后一次的卖出时机，买入时机是1位置

可能性3，1位置作为最后一次的卖出时机，买入时机是0位置

此时，best的值为

然后通过dp[1][3]加速dp[2][3]，通过dp[2][3]加速dp[3][3]......，所以二维dp的填写方式是按列填，

先填dp[1][0]，dp[1][2]一直到dp[1][k]，填好第一列；

然后填dp[2][0],dp[2][1]一直到dp[2][k]，填好第二列；

...

依次填好每一列，直到填完第N-1列。

枚举行为被优化，优化枚举后的完整代码如下：

主要思路：上一个问题中，令k=2就是本题的答案。

主要思路：因为有了冷冻期，所以每个位置的状态有如下三种：

定义三个数组，分别表示i位置这三种情况下的最大值是多少

显然有如下结论：

针对一个普遍位置i

最大收益就是如上三种方式的最大值。完整代码见：

由于三个数组有递推关系，所以可以用三个变量替换三个数组，做空间压缩，优化后的代码如下：

主要思路：由于没有冷冻期，所以在i位置的时候，状态只有两种

针对0位置

针对普遍位置i

完整代码如下：

同样的，两个数组都有递推关系，可以做空间压缩，简化后的代码如下：

原文链接：买卖股票的最佳时机系列问题 - Grey Zeng - 博客园

  我们在股票交易的时候，买入和卖出的时机是非常重要的，因为我们在买入和卖出的时候，对比一下股票的价格也是变化非常大的，我们只有在价格较低的时候买入，然后再选择在价格较高的时候卖出，我们才能够从中赚取更多的利润，这也是需要掌握一定的技巧和时机的。我们可以选择在股票下跌幅度较小的时候选择买入，然后在股票上涨幅度较大的时候选择卖出，这样也能够从中获得更多的利润。

  股票交易的时机是非常重要的，我们需要从各方面的去分析这款股票产品的情况，然后选择一个恰当的时机，再进行一系列的 *** 作，只有这样子才能够获得更多的利润。我们在购买股票产品之前，也要对这款股票产品的具体期限，还有一些注意事项进行详细的了解和咨询，通过全方面的了解再决定要不要去购买这款股票产品？

  我们可以在股票产品由下跌情况转为上涨情况的同时，有大部分的人去购买这款产品的时候，去购买股票产品是非常合适的。或者我们在一些涨停收盘的情况下，也是可以选择股票的买入，这都是一些较为重要的买入时机。我们同时也要根据自身的实际情况，来选择购买股票产品，避免给自己的生活造成一定的压力。

  购买股票的时候肯定是存在着各种各样的风险的，所以我们应该要预先做好相关的规划，并且对相应的风险进行控制。当出现了意料当中的风险之后，我们也要采取更为科学的手段去应对，这样子才能够有效的减少我们的经济损失。我们要拥有着清晰的头脑和意识，要掌握相应的技巧与手段。

1、挑选着正确的买进卖出时机

买进时机主要有四个：

(1)日K线显示某股票下跌二浪之后小幅波动，量缩至其流通股的千分之五以下，最好这样缩量盘整三天以上，或者在此区域阴线阳线交错，量能均衡且比前几日有所放大、可介入。

(2)如某股票最好跌至两年来的底部，即使跌破历史低价，也只是瞬间，其实是庄家在刻意打压吸筹，应果断买进。

(3)某股票小阴小阳或中阳一路稳步爬升，且有一段不小的涨幅，某一天(该股没有什么利空)突然出现一根下跌型的中阴或长阴，十有八九是庄家在震荡洗筹，可适当跟进。

(4)特别注意那些流通股在3500万以下，每股预期年化预期收益在0.40元以上的小盘绩优次新股，由于其极强的股本扩张能力，深得主力青睐，只要市盈率在30倍以下，当股价回落时，便可吸纳，中长线必有不俗的回报。

卖出时机主要也有四个：

(1)那些一年来没有动作过，而今有庄介入的个股，一般涨幅都会超过50%，多数可达100%。

慎重的投资者可在最低价上涨50%时抛出，进取型的可继续持筹看涨，在股价创下某高点后回落，跌幅超10%时获利了结。

(2)如某股票某天莫名其妙地拉出一根长红，且放巨量(达到其流通股的10%以上)，第二天一早可马上出局。

(3)某股票已有一段较大的涨幅，许多报纸和股评人士在圈点介绍之时，也是该派发的时候了。

(4)不赌最低点买进、最高点抛出，但求心平气和，买进股票后可定下一个标准，到心理价位后即可抛出，即使离场后还在上涨，也不必懊悔，毕竟你是股海中随波逐流的一叶小舟，根本无法与庄家抗争。

2、股票买进卖出的渠道

(1)当面委托。

即委托人以面对面的形式当面委托证券商，确定具体的委托内容与要求，由证券商受理股票的买卖。

(2)电话委托。

即委托人以电话形式委托证券商，确定具体的委托内容和要求，由证券商、经纪人受理股票的买卖交易。

(3)电传委托。

即委托人通过发电传给证券商，确定具体的委托内容和要求，委托证券商代理买卖股票。

(4)传真委托。

即委托人以传真的形式，将确定的委托内容与要求传真给证券商，委托他们代理买卖股票交易。

(5)信函委托。

即委托人用信函形式，将确定的委托内容和要求告知证券商，并委托他们代办买卖股票的交易。

我国深圳、上海主要是当面委托。

当面委托一般要委托人加以确认，受托证券商才予办理委托手续，而电话委托，则必须在证券商具备录音电话的条件下，才可办理。

委托人以电话委托买卖成交后应补交签章，如有错误原因不是由证券商造成的，证券商不负责任。

---