LeetCode Q188: Best Time to Buy and Sell Stock IV (hard)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Using DP. Iinspired buy solution of Sell Stock III, we keep track the price and profit at current transaction.

	class Solution {
	public:
	int maxProfit(int k, vector<int>& prices) {
	int maxProfit=0;
	if(prices.size()<2)
	return 0;
	if(k>prices.size()/2){
	for(int i=1; i<prices.size(); i++)
	maxProfit += max(prices[i]-prices[i-1], 0);
	return maxProfit;
	}
	int hold[k+1];
	int rele[k+1];
	for (int i=0;i<=k;++i){
	hold[i] = INT_MAX;
	rele[i] = 0;
	}
	for(int i=0; i<prices.size(); i++){
	for(int j=k; j>=1; j--){
	rele[j] = max(rele[j], prices[i]-hold[j]);
	hold[j] = min(hold[j], prices[i]-rele[j-1]);
	maxProfit=max(maxProfit, rele[j]);
	}
	}
	return maxProfit;
	}
	};

view raw Q188SellStockIV.cpp hosted with ❤ by GitHub