[AlgoExpert] Maximum Profit With K Transactions

Maximum Profit With K Transactions

  • Time : O(nk)
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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();
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/28/PS/AlgoExpert/maximum-profit-with-k-transactions/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.