CODEWITHSUNDEEP
arraysalgorithmfunctionmaxmin
Devendra Pratap Singh
Devendra Pratap Singh

Reputation: 81

Find max difference in array element

Sample case: a[]={1,4,2,5,10,5,4}; //output== 9
here we cannot change the order of element smaller always appear before bigger element The constraint are:

1<=n<=10^4
10^-6<=a[i]<=10^-6

Here is my code but it will fail on some test cases ,can someone find the error in this code. Thank You .

int maxDiff(int *a,int n)
{
   int MIN_value=INT_MAX;
   int MAX_vale=INT_MIN;
       for(int i=0;i<n;i++) {
        MIN_value=min(MIN_value,a[i]);
        MAX_value=max(a[i]-MIN_value,MAX_value);
    }
 return MAX_value;

}

Upvotes: 1

Views: 285

Answers (3)

Neil Lohana
Neil Lohana

Reputation: 26

When finding the min or max of an array it is best to set the initial max or min to the first possible outcome; in this case it would be number 1 - number 2. This is to ensure that INT_MAX and INT_MIN do not become your final answer. Alternatively, when finding the min you can use INT_MAX as the initial value for your min or vice versa.

int findMaxDiff(int* array, int n) {
    int max = array[i];
    int min = array[i];

    for(int i = 0; i < n; i++) {
         if(array[i] > max) {
            max = array[i]
         }
         if(array[i] < min) {
            min = array[i]
         }
    }
    return max - min;
}

Upvotes: 0

Zabuzard
Zabuzard

Reputation: 25903

The error must be in the logic of this line:

MAX_value=max(a[i]-MIN_value,MAX_value);

Use a debugger to test the method on different inputs and trace if MAX_Value gets the values assigned you expect it to get.

You may just set MAX_value correctly and return the difference afterwards:

MAX_value=max(MAX_value,a[i]);

Finally:

return MAX_VALUE - MIN_VALUE;

Be aware that if the difference is negative then the array was empty.

Edit: Compute the difference between the maximal value and the minimal value to the left of the maximal value (see comments):

possibleMinValue = min(possibleMinValue,a[i]);

oldMaxValue = MAX_value;
MAX_value=max(MAX_value,a[i]);

if (oldMaxValue != MAX_value) {
    // Found a new maximal value. Thus, possibleMinValue is a valid min value
    MIN_value = possibleMinValue;
}

Upvotes: 1

Vaibhav Bajaj
Vaibhav Bajaj

Reputation: 1934

Your function is wrong because, if it finds the minimum value at the end of the array, all your previous calculations of differences are invalidated. Your error is thus in the line:

MAX_value=max(a[i]-MIN_value,MAX_value);

A much better way to go about this would be:

int maxDiff(int *a,int n)
{
   if (n == 0 || n == 1)    //If list is empty or has 1 element, return 0
       return 0;
   int MIN_value=INT_MAX;
   int MAX_vale=INT_MIN;
       for(int i=0;i<n;i++) {
        MIN_value=min(MIN_value,a[i]);
        MAX_value=max(a[i],MAX_value);
    }
 return MAX_value - MIN_VALUE;

}

Upvotes: 1

Related Questions