题目描述（简单难度）

给一个数组，看作每天股票的价格，然后某一天买入，某一天卖出，最大收益可以是多少。可以不操作，收入就是 。

解法一 暴力破解

先写个暴力的，看看对题目的理解对不对。用两个循环，外层循环表示买入时候的价格，内层循环表示卖出时候的价格，遍历所有的情况，期间更新最大的收益。

解法二 双指针

这种数组优化，经常就是考虑双指针的方法，从而使得两层循环变成一层。思考一下怎么定义指针的含义。

代码的话就很好写了。

解法三

参考下边的链接。

-(In-case-if-interviewer-twists-the-input))

一个很新的角度，先回忆一下 53 题，求子序列最大的和。

用一个一维数组 dp [ i ] 表示以下标 i 结尾的子数组的元素的最大的和，也就是这个子数组最后一个元素是下边为 i 的元素，并且这个子数组是所有以 i结尾的子数组中，和最大的。

这样的话就有两种情况，

• 如果 dp [ i - 1 ] < 0，那么 dp [ i ] = nums [ i ]。

直接放一下最后经过优化后的代码，具体的可以过去 。

而对于这道题我们可以转换成上边的问题。

对于数组 1 6 2 8，代表股票每天的价格。

定义一下转换规则，当前天的价格减去前一天的价格，第一天由于没有前一天，规定为 0，用来代表不操作。

数组就转换为 0 6-1 2-6 8-2，也就是 0 5 -4 6。现在的数组的含义就变成了股票相对于前一天的变化了。

现在我们只需要找出连续的和最大是多少就可以了，也就是变成了 53 题。

换句话讲，买入卖出和连续的和形成了互相映射，所以问题转换成功。

代码在上边的基础上改一下就可以了。

而这个算法其实叫做 Kadane 算法，如果序列中含有负数，并且可以不选择任何一个数，那么最小的和也肯定是 0，也就是上边的情况，这也是把我们把第一天的浮动当作是 0 的原因。所以 max初始化成了 0。

更多 算法的介绍可以参考 维基百科。

总

这道题虽然是比较简单的，但是双指针的用法还是经常见的。另外解法三对问题的转换是真的佩服了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^