Simple O(n) and O(1) space solution


#1
 int max_idx = -1;
int maximum = INT_MIN;
int max_so_far = INT_MIN;
for(int i = 0;i<A.size();i++)
{
    if((max_idx==-1||max_idx==0)&&A[i]>maximum)
    {
        maximum = A[i];
        max_idx = i;
    }
    if(A[i]>max_so_far)
    max_so_far = A[i];
    if(maximum>A[i])
    {
        max_idx  =-1;
        maximum = max_so_far;        
    }
 // cout<<max_idx<<" "<<maximum<<endl;
}
if(max_idx==-1||max_idx==A.size()-1||max_idx==0)
return 0;
return 1;