седловые точки Матрицы

Когда-то очень давно, такой вопрос поднимался, но искали решение того, как это сделать на Сях. Сейчас уже не вспомню, но если на php и решение "в лоб", то могу предложить такой вариант:

Код (PHP):

1. $matrix = array(
2.     array(3, 12, 5, 2),
3.     array(3, 14, 16, 12),
4.     array(1, 19, 10, 14)
5. );
6. $maxL = array();  // максимальные значения в строках
7. $lineCnt = count($matrix[0]); // кол-во значений в строке
8. $tmpMin = array(); // временный массив для "разворота"  матрицы на 90°
9. foreach($matrix as $indx => $line){
10.     $max = max($line);
11.     $maxL[$indx][array_search($max, $line)] =  $max;
12.     for($i = 0; $i < $lineCnt; $i++){
13.         $tmpMin[$i][$indx] = $matrix[$indx][$i];
14.     }
15. }
16. $minC = array(); // минимальные значения в колонках
17. foreach($tmpMin as $indx => $line){
18.     $min = min($line);
19.     $minC[$indx][array_search($min, $line)] =  $min;
20. }
21. $sp = array(); // массив где будут выведены седловые точки или "no", где они не найдены
22. for($i = 0; $i < count($matrix); $i++){
23.     for($k = 0; $k < $lineCnt; $k++){
24.         if(isset($maxL[$i][$k],$minC[$k][$i])){
25.             $sp[$i][$k] =  $maxL[$i][$k];
26.         } else {
27.             $sp[$i][$k] =  'no';
28.         }
29.     }
30. }
31. print_r($sp); 

Нет времени рыскать по инету, но думаю, что для подобных задач, уже давно своё оптимальное колесо изобретено. Поэтому воспринимайте моё решение, как временное, пока вы не найдёте более достойное.

P.S. Более оптимальное решение (вроде бы работает чуть-чуть быстрее), но принцип по сути - тот же:

Код (PHP):

1. function find_saddle_points($arr) {
2.     $points = array();
3.     // проходимся по рядам матрицы
4.     foreach($arr as $i => $row) {
5.         // получем наибольшее значение из каждой строки
6.         $max = max($row);
7.         foreach($row as $j => $cell) {
8.             // только каждое максимальное значение 
9.             // проверяем - является ли оно минимальным в колонке
10.             if($cell == $max && min_in_col($arr, $cell, $j)) {
11.                 $points[$i][$j] = $arr[$i][$j];
12.             }
13.         }
14.     }
15.     return $points ? $points : 'Седловых точек не найдено';
16. }
17. function min_in_col($arr, $val, $col) {
18.     foreach($arr as $row) {
19.         // как только найдено хоть одно значение меньше - выходим
20.         if($val > $row[$col]) {
21.             return false;
22.         }
23.     }
24.     return true;
25. }
26. print_r( find_saddle_points($matrix) );