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(); }
|