[LeetCode]Best Time to Buy and Sell Stock II

这道题更简单，我们只要算出所有递增序列的和就行了。值得讨论的是根据这一题观察出来的其他结论，代码如下：

	public class Solution {
	public int maxProfit(int[] prices) {
	if (prices == null)
	return 0;
	int len = prices.length, max = 0;
	for (int i = 0; i < len - 1; i++) {
	int profit = prices[i + 1] - prices[i];
	max = profit > 0? max + profit: max;
	}
	return max;
	}
	}

view raw best time to buy and sell stock II.java hosted with ❤ by GitHub

我们可以看出以下两点：

• 递增序列的数量就是我们能最大化利润要买的次数，超过了这个次数，我们最大利润不会增加
• 假设现在能买k次，如果我们允许多买一次那么profit(k + 1) >= profit(k)，因为如果当前有序列不是递增序列，我们可以通过多买一次把它分成递增序列或者部分递增序列，或者除此之外还有别的递增序列，直到我们找到所有递增序列之后，利润不会增长

这道题还可以用DP的思路来解，用dp[i]表示前i + 1天的最大利润，我们有递推公式：

• localMax = max(dp[j] + prices[i] - prices[j]), where 0 <= j < i
• dp[i] = max(dp[i - 1], localMax)

代码如下：

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	int len = prices.size();
	if(len < 2)return 0;
	//localMax = max(dp[j] + prices[i] - prices[j]), where 0 <= j < i
	//dp[i] = max(dp[i - 1], localMax)
	int maxDiff = -prices[0], globalMax = 0;
	for(int i = 0; i < len; ++i)
	{
	int localMax = prices[i] + maxDiff;
	globalMax = max(globalMax, localMax);
	maxDiff = max(maxDiff, globalMax - prices[i]);
	}
	return globalMax;
	}
	};

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