# Accepted 8ms C++

• ``````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[j-1];
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, prev-prices[j-1]);
prev = f[j];
f[j] = std::max(f[j-1], S+prices[j]);
}
}
return f[n-1];
}``````

• can you explain what is f[i] array? I don't understand the loop of i [1..k] and the inner loop j [1..n). Thanks!

• First, it is DP solution. f[j] array save the max profit up to prices[j] with at most i transactions. So the loop of i =1:k is for number of transactions, and inner loop of j = 1 : n is for compute the profit. Hope this helps.

• For loop i = 1:K, for example, when i =1, means # of transactions is 1, why the inter loop has "n" transactions? What is f[j] for later loop?

• 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[i-1][j-1] and f[i][j-1], we simplify the memory footprint by use 1D table, f[j]. In the inner loop, prev means f[i-1][j-1], f[j-1] means f[i][j-1], 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][n-1]. Let me know if you have any confusion.

• Thanks, I got it. So one transaction has one buy and one sell. S here is "balance" at price j -1 up to i th transaction.

• To be precise, S is the balance before sell, f[j] the balance after sell.

• can we sort an array f[] which save f ,then select fisrt kth elements to solve this problem.

• Would you please be more specific on this? I do not quite understand your idea.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.