Maximum Profit With K Transactions

• Time : O(nk)
• Space : O(n)

c++

#include <vector>
using namespace std;

int maxProfitWithKTransactions(vector<int> prices, int k) {
	if(prices.empty()) return 0;
	int n = prices.size();
	vector<int> oddDp(n), evenDp(n);
	for(int i = 1; i <= k; i++) {
		vector<int>& prev = i & 1 ? evenDp : oddDp;
		vector<int>& cur = i & 1 ? oddDp : evenDp;
		int profit = INT_MIN;
		for(int j = 1; j < n; j++) {
			profit = max(profit, prev[j-1] - prices[j-1]);
			cur[j] = max(cur[j-1], profit + prices[j]);
		}
	}
  return k & 1 ? oddDp.back() : evenDp.back();
}