# C++ DP Solution, 12ms, with explanation and example

• ``````class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<=1) return 0;
int *dpLeft = new int[prices.size()+1]; dpLeft[0] = 0;
int tmp = prices[0];
for(int i = 1; i<prices.size(); i++){
tmp = min(tmp, prices[i]);
dpLeft[i] = max(dpLeft[i-1], prices[i]-tmp);
}
int *dpRight = new int[prices.size()]; dpRight[prices.size()-1] = 0;
tmp = prices[prices.size()-1];
for(int i = prices.size()-2; i>=0; i--){
tmp = max(tmp, prices[i]);
dpRight[i] = max(dpRight[i+1], tmp-prices[i]);
}
tmp = 0;
for(int i = 0; i<prices.size()-1; i++){
tmp = max(tmp, dpLeft[i]+dpRight[i+1]);
}
tmp = max(tmp, dpLeft[prices.size()-1]);
return tmp;
}
};
``````
• We can combine DP solution and Divide And Conquer Solution here. I will explain this with a simple example.Assume the stock is: 5,4,6,3,4,2,1,6. It is easy to understand that the max profit is 2(6-4)+5(6-1)=7.
• here, I use two array to cache profit, dpLeft and dpRight.
• dpLeft: cache the profit from left to right, the stock [5,4,6,3,4,2,1,6] generate dpLeft:[0,0,2,2,2,2,2,5]
• dpRight: cache the profit from right to left, stock [5,4,6,3,4,2,1,6] generate dpRight:[5,5,5,5,5,5,5,0]
• then, we use divide and conquer, the stock[5,4,6,3,4,2,1,6] , we compute profit from i = 0 to i = 7, and the maxProfit = max(maxProfit, dpLeft[i]+dpRight[i+1])
• finally, we finish this computation, the result is 7. the complexity is O(3n)=O(n)

• This post is deleted!

• Very clever!

• int *dpLeft = new int[prices.size()+1];
Why the size is "prices.size()+1" rather than "prices.size()"?

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