[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)，代码如下：

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	if(prices.empty())return 0;
	int len = prices.size(), globalMax = 0, minPrice = prices[0];
	for(int i = 1; i < len; ++i)
	{
	int localMax = prices[i] - minPrice;
	globalMax = max(globalMax, localMax);
	minPrice = min(minPrice, prices[i]);
	}
	return globalMax;
	}
	};

view raw Best Time to Buy and Sell Stock.cpp hosted with ❤ by GitHub