# Share my simple O(n) time solution

• ``````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], mmax-prices[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;
}
};``````

• 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[len-1];

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=len-1;i>=0;i--){
high=max(high,prices[i]);
result=max(result,high-prices[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

• You share the same idea with me. However, I am thinking if there is a solution where only one traversal of the list is needed. You know, we can expect questions like this in a job interview.

• I think in your first for loop, you don't need to keep update the result.
after the for loop, result must equals profits_history[prices.length - 1]

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