Как найти максимальное значение без ?/switch/if?

Question

[littleguga]

В голову пока пришло решение только с циклами.
Вот пример:

$arr = [1,2,3,4,5,6,98,65,190];
$max = $arr[0];
foreach($arr as $val){
     while($val > $max){
          $max = $val;
           break;
     }
}

Может есть более красивые решения?

upd:
Без привязки к языку. PHP, просто как пример взял. Интересует сам алгоритм.

Comments

[Anton]

на отсортированном массиве эту задачу легко решить. Вот если бы он был неотсортирован, то вот тут можно голову поломать.

[Mrrl]

Антон: Так он ведь не отсортирован! 65 идёт после 98.

Answer 1

[Alexander Movchan]

Можно написать функцию max без использования условных операторов:

def max_(a, b):
    return (a + b + abs(a-b)) / 2;

m = 0
arr = [1, 2, 3, 4, 5, 6, 98, 65, 190]
for val in arr:
    m = max_(m, val)

print(m)

Comments

[Mrrl]

Осталось написать abs без условных операторов :)

[Alexander Movchan]

Mrrl: Можно сделать с помощью битовых операторов, или извлечь корень из квадрата. Но и эти операции неявно содержат условные переходы (может быть на аппаратном уровне). Как уже сказали выше, задача подразумевает ветвление алгоритма и по другому её вряд ли можно решить.

Answer 2

[Андрей Буров]

$max = $arr[0];
foreach($arr as $val){
     $max = max($max, $val);
}

Comments

[littleguga]

С max() не интересно :)

Answer 3

[Дмитрий Ковальский]

stackoverflow.com/questions/5846156/get-min-and-ma... Вот тут что-то похожее решают.

Comments

[littleguga]

С max() не интересно :)

Answer 4

[alexxandr]

max(a, b) = (a > b)*a + (a < b)*b

при FALSE = 0; TRUE = 1

Answer 5

[Виталий Витренко]

Если интересуетесь именно алгоритмом, то вот отсюда :

Min and max. Given an array of N elements, find the min and max using as few compares as possible. Brute force: find the max (N-1 compares), then find the min of the remaining elements (N-2 compares).
Solution 1. Divide and conquer: find min and max in each half (2T(N/2) compares), return min of 2 and max of 2 (2 compares). T(1) = 0, T(2) = 1, T(N) = 2T(N/2) + 2. Recurrence solution: T(N) = ceil(3N/2) - 2.
Solution 2. Divide the elements into pairs and compare two elements in each pair. Put the smallest elements in A and the largest in B. If n is odd, put element n in both A and B. This requires floor(n/2) comparisons. Now directly compute the minimum in A (ceil(n/2) - 1 comparisons) and the maximum in B (ceil(N/2) - 1) comparisons. [In fact, this is best possible.]

Comments

[littleguga]

Спасибо за ответ!

Answer 6

[Mrrl]

Можно с битовыми операциями, в расчёте на 32-битную архитектуру:

var arr=new int[]{1,2,3,4,5,6,98,65,190};
    int max=arr[0];
    foreach(int x in arr){
        int y=max-x;
        max-=y&(y>>31);
    }

Answer 7

[FoxInSox]

Какой еще алгоритм? Операции ветвления это базовый элемент языка программирования. В вашем вопросе заложено использование по умолчанию оператора ветвления. И в приведенном вами случае while это лишь частный случай if.

Comments

[Олег Цилюрик]

... который и выполняется то максимум 1 раз.

[littleguga]

Попалась такая задачка с такой формулировкой, стало интересно, может я чего-то не знаю.