int maxProfit(int k, vector<int>& prices) {
int n = (int)prices.size();
if (n <= 1) return 0;
int fm = 0, km = 0;
for (int j = 1; j < n; j++) {
int f = prices[j]prices[j1];
if (f>0) {
fm += f;
km++;
}
}
if (k >= km) {
return fm;
} else {
int f[n], prev;
fill_n(f, n, 0);
for (int i = 1; i <= k; i++) {
int S = INT_MIN;
prev = f[0];
for (int j = 1; j < n; j++) {
S = std::max(S, prevprices[j1]);
prev = f[j];
f[j] = std::max(f[j1], S+prices[j]);
}
}
return f[n1];
}
Accepted 8ms C++


To make it simple, let us do DP with 2D table. f[i][j], So it represents max profit can be made with at most i transactions up to prices[j]. the inner loop "n" means you have n prices. Since f[i][j] computation only depends on f[i1][j1] and f[i][j1], we simplify the memory footprint by use 1D table, f[j]. In the inner loop, prev means f[i1][j1], f[j1] means f[i][j1], f[j] means f[i][j]. If you substitute these and you will get a clear picture. Surely, in the end, it really means f[k][n1]. Let me know if you have any confusion.