The original question can be found here.

Lets start from an elegant the solution :

` ````
```class Solution {
public int maxProfit(int k,int[] prices) {
if (prices.length<2 || k==0) return 0;
int[] profits = new int[k+1];
int[] balance = new int[k];
Arrays.fill(balance,-prices[0]);
for (int p : prices) {
for (int i=0;i

This solution would run in O(n*k). if we dont mind getting our hands dirty, it can be better implemented and then explained like that:

` ````
```class Solution {
public int maxProfit(int k,int[] prices) {
if (prices.length<2 || k==0) return 0;
int[] profits = new int[k+1];
int[] balance = new int[k];
balance[0]=-prices[0];
int transactions=1;
for (int p : prices) {
if (transactionsprofits[transactions-1]) {
balance[transactions]=profits[transactions]-p;
transactions++;
}
for (int i=0;i

Now it would run in O(n*m) where is the trade count in the optimal solution. commonly m<<k. Lets begin with the explanation, We’ll keep track of the following loop invariants:

will hold the max profit we can get for*profits[i]**i*efficient full transactions.

*profits[0]* is always 0 since that’s the profit when we make no transactions, *profits[1]* is the maximal profit we could have with 1 efficient full transaction and so on.

will hold the optimal balance we would have if we do*balance[i]**i*efficient full transactions and then an efficient buy.

since we have only have a buy for balance[0], it will eventually hold the negate of the minimal price, balance[1] will be the best balance after doing one full transaction efficiently and followed by a buy, and so on.

Whenever we find that ** profits[i]>profits[i-1] ** it would mean that we can increase our profits by doing one more full transaction after i-1 efficient full transactions, so we search for this to hold, and when it does we start to work on profits for next i.

We try to maximize our ** balance[i]** which consists of the

**which is the profit we made so far, and paying for our following buy. for every new price we examine if we improve our balance when buying at that price, if we don’t we stay with the previous balance.**

*profits[i]*Then for ** profits[i+1] **we take the optimal

**and we need to add the price we get if we sell to complete the i+1 trade transaction, we will not do the sell if we previously had a better setup.**

*balance[i]*Eventually we return ** profits[transaction]** which is the max profit for the optimal count of transactions.