# Extend most voted of III, O(kN) time, O(N) space, Java

• In below code, maxProfit_v0() is the base version, and maxProfit is space optimized version.
buy[i][j]: most profit get from the first j days with at most i buy actions.
sell[i][j]: most profit get from the first j days with at most i sell actions.

``````public class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length < 2)
return 0;
if (k >= prices.length)
return maxProfitInfinite(prices);
int N = prices.length;
int[] sellOneLess = new int[N + 1];
int[] sell= new int[N + 1];
int[] buy = new int[N + 1];
for (int i = 1; i <= k; i++) {
sell[0] = 0;
for (int j = 1; j <= N; j++) {
sell[j] = Math.max(buy[j - 1] + prices[j - 1], sell[j - 1]);
buy[j] = Math.max(sellOneLess[j - 1] - prices[j - 1], buy[j - 1]);
}
for (int j = 0; j <= N; j++) {
sellOneLess[j] = sell[j];
}
}
return sell[N];
}

// base version of the above maxProfit()
public int maxProfit_v0(int k, int[] prices) {
if (prices == null || prices.length < 2)
return 0;
if (k >= prices.length)
return maxProfitInfinite(prices);
int N = prices.length;
int[][] buy = new int[k + 1][N + 1];
int[][] sell = new int[k + 1][N + 1];
for (int i = 1; i <= k; i++) {
sell[i][0] = 0;
for (int j = 1; j <= N; j++) {
sell[i][j] = Math.max(buy[i][j - 1] + prices[j - 1], sell[i][j - 1]);
buy[i][j] = Math.max(sell[i - 1][j - 1] - prices[j - 1], buy[i][j - 1]);
}
}
return sell[k][N];
}

public int maxProfitInfinite(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
profit += Math.max(prices[i] - prices[i - 1], 0);
}
return profit;
}
}
``````

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