[LeetCode]Best Time to Buy and Sell Stock

如果我们把相邻的price算一个差来算出新的数组，那么这一道题和max subarray是一样的。Divide and Conquer方法是类似的，这里我们只讨论DP解法，GlobalMax[i]代表到price[i]位置的最大收益；localMax[i]代表代表到price[i]位置的最大收益并且最优一次交易结束在price[i]。DP方程：

• GlobalMax[i] = GlobalMax[i - 1] + localMax[i]
• localMax[i] = max(localMax[i - 1] + price[i] - price[i - 1],  0);

时间复杂度O(n)，空间可以优化成O(1)，代码如下：