# DP, O(KN) Time,O(n) Space, cpp , solution.

• if k >= n/2, we can have transactions any time, it can be solved by O(n).

else, we can do it in DP.

use dp[k][i+1] represents, The max profit of using [0,i] data and k transactions.

So we have:

dp[k][i+1] = max(dp[k-1][i+1], dp[k][i], max( dp[k-1][j] + prices[i] - prices[j] ))

= max(dp[k-1][i+1], dp[k][i], prices[i] + max( dp[k-1][j] - prices[j] )) { 0 <= j < i }

it can be solved by O(kn).

The Code:

``````class Solution {
public:
int maxProfit_all(vector<int> &prices) {
int n = prices.size();
int sum = 0;
for(int i = 1;i < n;i++){
if(prices[i] > prices[i-1]){
sum += prices[i] - prices[i-1];
}
}
return sum;
}
int maxProfit(int k, vector<int> &prices) {
int n = prices.size();
if(k >= n/2){
return maxProfit_all(prices);
}
int dp[2][n+1];
memset(dp,0,sizeof(dp));
for(int t = 1; t <= k; t++){
int cur_max = 0x80000000;
dp[t%2][0] = 0;
for(int i = 0; i < n; i++){
dp[t%2][i+1] = max(dp[(t+1)%2][i+1],max(dp[t%2][i],prices[i] + cur_max));
cur_max = max(cur_max,dp[(t+1)%2][i] - prices[i]);
}
}
return dp[k%2][n];
}
};``````

• thank you very much, i think the key insight is
max( dp[k-1][j] - prices[j] ))
can be kept in a tmp value when we loop through i

• This post is deleted!

• Do some improvement base on your solution.
Just consider the peak value in prices. So build a new vector, peaks, only contains the peak values in prices.
Then use the same algorithm on peaks instead of prices.

The Codes:

``````class Solution {
public:
int maxProfit(int k, vector<int> &prices) {
int res=0,n=prices.size(),maxTrans=0;
if(n==0)return 0;
vector<int>peak;
for(int i=1;i<n;++i)
if(prices[i]>prices[i-1])res+=prices[i]-prices[i-1];

peak.push_back(prices[0]);
for(int i=1;i<prices.size()-1;++i)
if((prices[i-1]<=prices[i] && prices[i]>prices[i+1])||(prices[i-1]>=prices[i] && prices[i]<prices[i+1]))
peak.push_back(prices[i]);
if(n>1)peak.push_back(prices[n-1]);

if(k>=peak.size()/2)return res;
int n1 = peak.size();
int dp[2][n1+1];
memset(dp,0,sizeof(dp));
for(int t = 1; t <= k; t++){
int cur_max = 0x80000000;
dp[t%2][0] = 0;
for(int i = 0; i < n1; i++){
dp[t%2][i+1] = max(dp[(t+1)%2][i+1],max(dp[t%2][i],peak[i] + cur_max));
cur_max = max(cur_max,dp[(t+1)%2][i] - peak[i]);
}
}
return dp[k%2][n1];
}
};``````

• Thanks for the nice improvement.

• There is a more clean and concise cpp solution.When `k<size/2`:Time complexity is O(kn), space complexity can be O(n) because this DP only uses the result from last step:

``````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];
}
};``````

• Good improvement since there will be a better chance to have k >= peak.size/2 and use the simple method.

Though I think the calculation of res should be put inside the if block, you don't need to do this for other cases.

• Hi, Insulator. I confuse that why you omit to compute "max( dp[k-1][j] - prices[j] ) { 0 <= j < i }" like loop, and compute the cur_max "cur_max = max(cur_max,dp[(t+1)%2][i] - prices[i]);" directly. Is there any special idea? thanks.

• I modified the code from @yulingtianxia a little for better understanding.

Basically, in the k-th iteration:

buy[k][i] represents the maximum profit if you buy the stock on day i after at most k - 1 transactions.

``````buy[k][i] = max(buy[k - 1][i], sell[k - 1][i - 1] - prices[i])
``````

sell[k][i] represents the maximum profit if you sell the stock on day i after at most k - 1 transactions.

``````sell[k][i] = max(sell[k - 1][i], buy[k - 1][i - 1] + prices[i])
``````

we can reuse the buy[i - 1] and sell[i - 1] as buy[i] and sell[i].

The code:

``````class Solution {
public:
int maxProfit(int k, vector<int> &prices) {
int N = prices.size();
if (k == 0 || N < 2) return 0;

if (k > N / 2) {
int sum = 0;
for (int i = 1; i < N; i++){
if (prices[i] > prices[i - 1]){
sum += prices[i] - prices[i - 1];
}
}
return sum;
}