[LeetCode]Best Time to Buy and Sell Stock IV

根据Max Subarray III我们可以知道这一题是有时间O(k* n)，空间O(k* n)的解法的。GlobalMax[i][j]代表进行i次操作，在前j天之内的最大利润；localMax[i][j]代表代表进行i次操作，在前j天之内的最大利润，并且最后一次操作完成在第j天。DP方程如下：

• GlobalMax[i][j] = max(GlobalMax[i][j - 1], localMax[i][j]);
• localMax[i][j] = max(GlobalMax[i - 1][k] + price[j] - price[k]), 其中0 <= k <= j；

我们可以看到max(GlobalMax[i - 1][k] + price[j] - price[k])是取决于max(GlobalMax[i - 1][k] - price[k])这个值的，我们只要一直维护这个的最大值就可以了（这个值的代表什么笔者并不明确），这个比Max Subarray III的线性做法更直观，我们可以在线性时间构建GlobalMax[i]。代码如下：

	public class Solution {
	public int maxProfit(int[] prices) {
	if (prices == null)
	return 0;
	int len = prices.length;
	if (len < 2)
	return 0;
	return maxProfitInKTimes(prices, 2);
	}
	private int maxProfitInKTimes(int[] prices, int k) {
	int len = prices.length;
	//max profit in i operations in j days
	int[][] globalMax = new int[k + 1][len + 1];
	for (int i = 1; i <= k; i++) {
	int diff = Integer.MIN_VALUE;
	for (int j = 0; j < len; j++) {
	diff = max(diff, globalMax[i - 1][j + 1] - prices[j]);
	globalMax[i][j + 1] = max(globalMax[i][j], diff + prices[j]);
	}
	}
	return globalMax[k][len];
	}
	private int max(int a, int b) {
	return a >= b? a: b;
	}
	}

view raw best time to buy and sell stock III v-2.java hosted with ❤ by GitHub

我们可以只用一维数组解决这个问题，这样空间复杂度可以优化到O(n)，但是这样仍然过不了test case最后几组数据，这是因为那几组数据k远远大于n，这样导致整体的时间复杂度k * n很高，但是值得注意的是，当允许交易次数多于n / 2的时候（也就是第一天买，第二天卖，第三天买，第四天卖。。。我们不会第一天买，第二天卖，然后第二天买，第三天卖，这样的话就相当于第一天买第三天卖），我们永远可以达到给定prices数组的最大利润，这样的话，题目就变为Best Time to Buy and Sell Stock II，我们可以在O(n)的时间内解决。所以我们特别check这种情况即可，代码如下：

	class Solution {
	public:
	int maxProfit(int k, vector<int>& prices) {
	int len = prices.size();
	if(!len)return 0;
	if(k > len / 2)return maxProfit(prices);
	//dp[i][j] represent maxProfit in first j + 1 days and do at most i transactions
	vector<int> dp(len, 0);
	for(int i = 1; i <= k; ++i)
	{
	//dp[i][j] = max(max(dp[i - 1][k] + prices[j] - prices[k]), dp[i][j - 1]), where k <= j
	//we can do this in one pass, we maitain the max value of dp[k] - prices[k]
	int maxVal = dp[0] - prices[0];
	for(int j = 1; j < len; ++j)
	{
	maxVal = max(maxVal, dp[j] - prices[j]);
	dp[j] = max(maxVal + prices[j], dp[j - 1]);
	}
	}
	return dp[len - 1];
	}
	private:
	//maximum profit we can get given prices array
	int maxProfit(vector<int>& prices)
	{
	int res = 0;
	for(int i = 1; i < prices.size(); ++i)
	{
	//as long as there is increase in price, we can get profit
	if(prices[i] > prices[i - 1])
	res += prices[i] - prices[i - 1];
	}
	return res;
	}
	};

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