O(n) with O(1) space . Easy solution


#1

int Solution::maxProfit(const vector &a)
{
int n=a.size();
if(n==0)
return 0;
int min1=0,f=0;
int max1=0;
int diff=max1-min1;
for(int i=1;i<n;i++)
{
if(a[i]>a[max1])
{
max1=i;
f=0;
}
if(a[i]<a[min1])
{
min1=i;
f=1;
}
if(f==1)
{
if(i>min1)
{
diff=max(diff,a[i]-a[min1]);
}
}
if(max1>min1)
{
diff=max(diff,a[max1]-a[min1]);
}
}

return diff;

}