Easy C++ solution. DP


#1

int Solution::maxProfit(const vector &A)
{
if(A.size()<2)
{
return 0;
}
int n=A.size(),i,profit1=0,profit2=0;
int dp_sell[n],dp_buy[n];
int least_so_far=A[0],max_after=A[n-1];
dp_sell[0]=0;
dp_buy[n-1]=0;
for(i=1;i<n;i++)
{
least_so_far=min(least_so_far,A[i]);
profit1=A[i]-least_so_far;
dp_sell[i]=max(dp_sell[i-1],profit1);
}
for(i=n-2;i>=0;i–)
{
max_after=max(max_after,A[i]);
profit2=max_after-A[i];
dp_buy[i]=max(dp_buy[i+1],profit2);
}
int res=0;
for(i=0;i<n;i++)
{
res=max(res,dp_sell[i]+dp_buy[i]);
}
return res;
}