题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例

<code>输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。/<code>

<code>输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 

     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。/<code>

<code>输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。/<code>

题解

这道题属于一道求最优解的题目，这类题目需要经过一系列的步骤，每个步骤又有不同的选择，而贪心算法，则是在每一步做出在当时看起来是最优的选择，得到局部的最优解，最终导致全局的最优解。

这道题的贪心流程，应该是下面这样：

在当天，我们要判断下昨天与今天的股价差，如果有上升，也就是今天比昨天高，就应该把正数的差额作为当前最优解，计入总利润中，一步一步往下走，走到最后一天，则得到了最终的最大利润。

这道题目中的每一步就是： “今天的股价 - 昨天的股价”。

每一步的结果包括了：正数、负数、零。

每一步的最优解，根据题目来看的话，也就是最大的意思，也就是贪心所有的正数差。

但这个算法不代表真正的交易，只代表了计算过程，它可以得到最优解，就以示例中的[1,2,3,4,5]为例，我们在1、2、3、4、5的时候，根据这个算法流程，我们应该是

计算prices[i]-prices[i-1]的差是不是正数，是的话则计入总利润，也就是

总利润 = (prices[1]-prices[0]) + (prices[2]-prices[1]) + (prices[3]-prices[2]) + (prices[4]-prices[3]) = prices[4] - prices[0]。

可以看出，算法的流程上如果看做真正的交易的话，买进第一天的，第二天卖出，然后又买入第二天的，第三天卖出，直到最后一天，但是按照规则，不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票），但这个流程的结果又可以看做且等价为：在第一天买入，在最后一天卖出，能得到最大的利润（prices[4] - prices[0]），也就是真正的交易过程。

可能有朋友就有疑虑了，为什么能这么笃定，贪心算法得到的解就一定是最优解呢，我们可以这样来想一下：

贪心算法根据每步的最优解得到结果，在这道题目中，每步的最优解也就是正数，之所以每一步的结果加起来会是最优解，我们可以假设，贪心算法得到的最终结果并不是一个全局最优解，那么就存在其他方式可以得到最优解，但是贪心算法是每次都得到最优也就是正数，那么其他算法，如果他拿的不是正数，而是零，那此时最终结果肯定比贪心得到的值小，如果它拿到的是正数，那最终结果就等于贪心得到的值，如果它拿到的是负数，那最终结果就肯定比贪心得到的值小。

也就是说，除了贪心算法，找不到能得到更大的结果的算法，所以贪心算法可以通过局部最优得到全局最优解。

下面附上贪心算法的java代码图