# A C++ solution by DP, O(n^2) time O(n) space

• By the idea of DP, keep an array maxprofit, such that maxprofit[i] is the max profit using prices[0] to prices[i].

The recursion is given by maxprofit[i] = max{maxprofit[i - 1], prices[i] - prices[j] + maxprofit[j - 2]: j = 0,1,...,i}, where maxprofit[-1] = maxprofit[-2] = 0.

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n <= 1)
return 0;

vector<int> maxprofit (n, 0);
maxprofit[1] = max(prices[1] - prices[0], 0);

for(int i = 2; i < n; i ++){
int temp = 0;
for(int j = i; j >= 2; j --){
temp = max(temp, maxprofit[j - 2] + prices[i] - prices[j]);
}
temp = max(temp, prices[i] - prices[1]);
temp = max(temp, prices[i] - prices[0]);
maxprofit[i] = max(temp, maxprofit[i - 1]);
}

return maxprofit[n - 1];
}
};``````

• ``````{class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
// dp[1][i] = max(dp[0][p] + prices[i] - prices[p + 1], dp[1][p] + prices[i] - prices[p + 2])
for (int i = 1; i <= prices.size(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (j < i - 1 && prices[i - 1] > prices[j + 1]) buy[i] = max(buy[i], buy[j] + prices[i - 1] - prices[j + 1]);
}
}
}
``````

};
}

timeout

• The translation for Java:

``````public int maxProfit(int[] prices) {

int n = prices.length;
if(n <= 1) {
return 0;
}

int[] maxprofit = new int[n];
maxprofit[1] = Math.max(prices[1] - prices[0], 0);

for(int i = 2; i < n; i++) {
int temp = 0;
for(int j = i; j >= 2; j --) {
temp = Math.max(temp, maxprofit[j - 2] + prices[i] - prices[j]);
}
temp = Math.max(temp, prices[i] - prices[1]);
temp = Math.max(temp, prices[i] - prices[0]);
maxprofit[i] = Math.max(temp, maxprofit[i - 1]);
}

return maxprofit[n - 1];
}``````

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