# A Concise DP Solution in Java

• The general idea is DP, while I had to add a "quickSolve" function to tackle some corner cases to avoid TLE.

DP: t(i,j) is the max profit for up to i transactions by time j (0<=i<=K, 0<=j<=T).

``````    public int maxProfit(int k, int[] prices) {
int len = prices.length;
if (k >= len / 2) return quickSolve(prices);

int[][] t = new int[k + 1][len];
for (int i = 1; i <= k; i++) {
int tmpMax =  -prices[0];
for (int j = 1; j < len; j++) {
t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
}
}
return t[k][len - 1];
}

private int quickSolve(int[] prices) {
int len = prices.length, profit = 0;
for (int i = 1; i < len; i++)
// as long as there is a price gap, we gain a profit.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
}``````

• Awesome solution. I got the idea which has O(k*n^2) time complexity. That's why I got TLE in large test cases. Could you please explore your idea a little bit so that we can have a better understanding on this.

• Because buy and sell prices may not be the same, when k>len/2, that means we can do as many transactions as we want. So, in case k>len/2, this problem is same to Best Time to Buy and Sell Stock III.

t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax) gives us the maximum price when we sell at this price;
tmpMax = Math.max(tmpMax, t[i - 1][j] - prices[j]) gives us the value when we buy at this price and leave this value for prices[j+1].

• Actually,
tmpMax = Math.max(tmpMax, t[i - 1][j] - prices[j]); - this is kind of misleading
should be
tmpMax = Math.max(tmpMax, t[i - 1][j-1] - prices[j]); - by changing to this, it is still acceptable, and easy to understand.

tmpMax means the maximum profit of just doing at most i-1 transactions, using at most first j-1 prices, and buying the stock at price[j] - this is used for the next loop.

• Good point. Modified. Thanks.

• int[][] t = new int[k + 1][len]; could be changed to one dimension.

• Here is my cpp solution.Very similar to yours : )

``````class Solution {
public:
int maxProfit(int k, vector<int> &prices) {
int size = (int)prices.size();
if (k==0||size<2) {
return 0;
}
if (k>size/2) {
int sum = 0;
for(int i = 1;i < size;i++){
if(prices[i] > prices[i-1]){
sum += prices[i] - prices[i-1];
}
}
return sum;
}
vector<int> sell(k,0);
for (int i=0; i<size; i++) {
for (int j=k-1; j>=0; j--) {
}
}
return sell[k-1];
}
};``````

• if (k > len / 2) => if (k >= len / 2) will work.

• I wonder if one can get better than O(k*n) with DP. Without DP, using a fancy heap one can get down to O(n*log(n))

• When j = 0, t[i - 1][j - 1] - prices[j] = t[i - 1][-1] - prices[0]. Thus "int tmpMax = t[i - 1][0] - prices[0];" is misleading. I prefer "int tmpMax = 0 - prices[0];", regarding t[i - 1][-1] as 0.

• And initial tmpMax could be

int tmpMax = - prices[0];

because t[i - 1][0] is always equal to zero.

• This solution implies that in each day, 2 transactions can be done (1 sell and 1 buy) which is not mentioned in the problem description. I think this should be added to the problem to eliminate misunderstanding.

• what's the meaning of sell[] and buy[]?

• sell[i]/buy[i] is the rest money after sell/buy the stock at most i times. we have zero money at first.

• You don't have to really sell at that day. The first time you calculated profit of if you sell at day j, then later you use (that value - day j price + day i price) to calculate what profit you will get if you don't sell at day i but sell later.

• This post is deleted!

• C++ version, inspired by yulingtianxia

``````int maxProfitInf(vector<int> &prices) {
int buyin = INT_MAX, profit = 0;
for(auto & price : prices) {
}
return profit;
}

int maxProfit(int k, vector<int> &prices) {
if(k == 0 || prices.empty()) return 0;
// Max profit by k transaction from 0 to i
const int n = prices.size();
if(k >= n / 2) return maxProfitInf(prices);

// balance - the balance with at most j transactions with item 0 to i
// profit - the profit with at most j transactions with item 0 to i
vector<int> balance(k + 1, INT_MIN), profit(k + 1);

for(int i = 0; i < n; ++i) {
for(int j = 1; j <= k; ++j) {
balance[j] = max(profit[j - 1] - prices[i], balance[j]); // whether to buy at prices[i]
profit[j] = max(balance[j] + prices[i], profit[j]); // whether to sell at prices[i]
}
}

return profit[k];
}``````

• Nice Solution ~ I would say your answer is much more intuitive ! Really help me have a good understanding on the problem.

• My question is how to think of questions like this. I mean how to come up with the solution?

• if (k >= len / 2) return quickSolve(prices);
should this be k >= len-1 ?
say if the prices is [1,2,3,4] k = 2
it will pass to quickSolve method, but the quickSolve method will make 3 transactions instead of 2

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