# O(k) space simple and easy to understand java solution

• The key function is:

The first function means that we are now at price, and we are in the ith transaction, and we are gonna ending with a sell, we can either do nothing which refers to sell[i], or we can sell the stock which means we must do buy[i] first and thus refers to buy[i]+price.
The second function works in the similar way, we can either do nothing which refers to buy[i] or we can sell the stock in transaction i-1 first and buy the stock now, which refers to sell[i-1]-price, apparently, we need the max value of the two.
The initial value of buy and sell can be thought as follows:
we init buy to Integer.MIN_VALUE to confirm that it will be updated in the loop because of the Math.max function
we init sell to 0 because we actually has nothing to sell and at first we got 0 money, the result will be our pure profit
the return value is sell[k] which means we end with the sell of the kth transaction

``````public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) {
int max = 0;
for (int i = 1; i < n; i++)
max += Math.max(0, prices[i] - prices[i - 1]);
return max;
}
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
Arrays.fill(sell, 0);
for (int price : prices) {
for (int i = k; i > 0; i--) {
sell[i] = Math.max(sell[i], buy[i] + price);
}
}
return sell[k];
}
``````

• nice solution! easy to follow! Had one question, how did you figure out prove to yourself that if k >= n/2 then the max profit was simply the sum of all possible profits?

• @smarin a transaction consists of two events: buy and sell, so n events consisits of at most n/2 transactions.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}