Easy cpp solution using prefix array


#1

Comment body goes here.
typedef long long int ll;
int Solution::maxProfit(const vector &A) {
int n=A.size();
if(n==0)
return 0;
ll dp[n];
dp[n-1]=A[n-1];

for(int i=n-2;i>=0;i--)
{
    dp[i]=max(A[i],(int)dp[i+1]);
}

 ll ans=0;
for(int i=0;i<n;i++)
{
    if((dp[i]-A[i])>0)
    {
        ans=max(ans,dp[i]-A[i]);
    }
}
return (int)ans;

}