```
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)