Simple CPP solution O(n)


#1

int Solution::solve(vector &A) {
int n = A.size();
int max, min;
if(n%2 == 0){
if(A[0] < A[1]){
max = A[1];
min = A[0];
}
else{
max = A[0];
min = A[1];
}

    for(int i=2;i<n;i++){
        if(A[i] > max)
            max = A[i];
        else if(A[i] < min)
            min = A[i];
    }
}
else{
    max = min = A[0];
    for(int i=1;i<n;i++){
        if(A[i] > max)
            max = A[i];
        else if(A[i] < min)
            min = A[i];
    }
}
return max + min;

}


#2

@sandeepkumar318 we have to minimize the number of comparisons…


#3

Yes, I learnt this algo from CLRS book. you can also refer there


#4

but how is this code minimizing comparisons…i think it will be 2*N comparisons only


#5

if numbers are in decreasing order then it will take 2*N comparisons…