Максимальное различие между двумя элементами

Учитывая массив целых чисел, мне нужно выяснить максимальную разницу между любыми двумя элементами, чтобы большее число появлялось после меньшего числа в массиве. Я использовал простой подход и воспользовался минимальное число встречается до сих пор сохраняя след 2 вещиМаксимальное различие между двумя элементами

разница 1.Maximum

номер 2.Minimum посетили до сих пор.

int min_element=arr[0]; 
    int diff=arr[1]-arr[0]; 
    for(i=1;i<n;i++) 
    { 
     if(arr[i]-min_element>diff) 
      diff=arr[i]-min_element; 
     if(arr[i]<min_element) 
      min_element=arr[i]; 
    } 
    return diff;

Есть ли лучший способ решения этой проблемы?

источник

2013-04-05 poorvankBhatia

Так как у вас есть * рабочий * код и вы просто ищете отзыв, вы можете рассмотреть этот вопрос для [обзора кода] (http://codereview.stackexchange.com/). – Mike

У вас все в порядке. Вы можете использовать различные трюки, чтобы ускорить его с помощью постоянного фактора, но только постоянным фактором (для него тривиально требуется время Ω (n), которое достигается вашей реализацией). Если это не является существенным узким местом производительности для вашей программы, убедитесь, что ваш компилятор включен, и перейдите к следующей проблеме. –

Nitpick: вы не проверяете, что 'arr [1]' больше, чем 'arr [0]'. Пока данные не сортируются в обратном (убывающем) порядке, он должен сортироваться, но вам нужно подумать о граничных условиях (что, если есть только два элемента, и они не в порядке возрастания?). –

В его нынешнем виде ваш алгоритм является оптимальным, с постоянным коэффициентом.

Чтение массива из n целых чисел принимает Ω(n). Ваш алгоритм O(n), так что вы хороши.

источник

2013-04-05 14:22:55 abeln

Максимальное различие между двумя элементами

ответ

Смежные вопросы