Найти максимальное значение в элементе массива

Question

Примера случай: a[]={1,4,2,5,10,5,4}; //output== 9
здесь мы не можем изменить порядок элементов меньших всегда предстают перед большим элементом ограничения является:

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

Вот мой код, но он не сможет на некоторых тестовых примерах, кто-то может найти ошибку в этом коде. Спасибо.

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; 

} 

Answer 1

Ошибка должна быть в логике этой линии:

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

Используйте отладчик для тестирования метода на различных входах и трассировки, если MAX_Value получает значения, присвоенные вы ожидаете получить.

Вы можете просто установить MAX_value правильно и вернуть разницу после:

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

Наконец:

return MAX_VALUE - MIN_VALUE; 

Имейте в виду, что если разница отрицательна, то массив был пуст.

Edit: Вычислить разность между максимальным значением и минимальным значением к влево от максимального значения (см комментарии):

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; 
} 

Answer 2

Ваша функция не так, потому что, если он находит минимальное значение в конце массива все ваши предыдущие вычисления различий недействительны. Ваша ошибка, таким образом, в строке:

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

Намного лучше идти об этом будет:

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; 

} 

Answer 3

При нахождении мин или макс массива это лучше всего установить начальный максимум или мин до первого возможного результата; в этом случае это будет номер 1 - номер 2. Это должно гарантировать, что INT_MAX и INT_MIN не станут вашим окончательным ответом. Кроме того, при поиске мин вы можете использовать INT_MAX в качестве начального значения для вашего мин или наоборот.

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; 
}