C++ Solution O(n)


#1

int Solution::maxSubArray(const vector &A) {

int n=A.size();
int i,flag=0;
int sum=0,max_sum=INT_MIN;

    for(i=0;i<n;i++)                           //To check if any no. is positive
    {
        if(A[i]>=0)
        {
            flag=1;
            break;
        }
    }
    
    if(flag==0)                                //For all negative number array
    {
        for(i=0;i<n;i++)
        {
            if(A[i]>max_sum)
            max_sum=A[i];
        }
        return max_sum;
    }
    else                                       //Kadane's Algorithm
    {
        for(i=0;i<n;i++)
        {
            sum+=A[i];
            if(sum>max_sum)
            {
                max_sum=sum;
            }
            if(sum<0)
            {
                sum=0;
            }
        }
        return max_sum;
    }

}