class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.empty())
return 0;
// dp stores the max profit before index i
vector<int>dp;
dp.resize(prices.size());
dp[0] = 0;
int mmin = prices[0];
for (int i = 1; i < prices.size() ; i++)
{
if (mmin>prices[i])
{
mmin = prices[i];
dp[i] = dp[i  1];
}
else
{
dp[i] = max(dp[i  1], prices[i]  mmin);
}
}
// dp1 stores the max profit after index i
vector<int>dp1;
dp1.resize(prices.size());
dp1[prices.size()1] = 0;
int mmax = prices.back();
for (int i = prices.size()2; i >=0 ; i)
{
if (mmax<prices[i])
{
mmax = prices[i];
dp1[i] = dp1[i + 1];
}
else
{
dp1[i] = max(dp1[i + 1], mmaxprices[i]);
}
}
// res = max{dp[i]+dp1[i]}
int res = 0;
for (int i = 0; i < prices.size() ; i++)
{
if (res < dp[i] + dp1[i])
res = dp[i] + dp1[i];
}
return res;
}
};
Share my simple O(n) time solution


I think mine is really simple.
class Solution { public: int maxProfit(vector<int> &prices) { if (prices.size()<2) return 0; int len=prices.size(),result=0; int low=prices[0],high=prices[len1]; vector<int> profits_history(len,0); for (int i=0;i<len;i++){ low=min(low,prices[i]); result=max(result,prices[i]low); profits_history[i]=result; } for (int i=len1;i>=0;i){ high=max(high,prices[i]); result=max(result,highprices[i]+profits_history[i]); } return result; } };

Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example