Еврейский алгоритм (жадный) обьясните код

[nelo_001]

Это Дан массив из N целых чисел. Найти три числа, произведение которых максимально.

var
   n : longint; 
   max1, max2, max3 ,pr : longint;
   min1, min2 : longint;
     
   k : integer; 
   i : longint;
begin
     assign(input, 'input.txt');
     reset(input);
     assign(output, 'output.txt');
     rewrite(output);
     max1 := -10000; max2 := max1; max3 := max1;
     min1 := 10000; min2 := min1;
     readln(n);
    
     for i:=1 to n do
      begin
         read(k);
         if k > max1 then 
           begin 
 max3 := max2; max2 := max1; max1 := k; 
           end 
         else
         if k > max2 then 
           begin 
 max3 := max2; max2 := k; 
           end 
         else
         if k > max3 then 
              max3 := k;

         if k < min1 then 
          begin 
              min2 := min1; min1 := k; 
          end 
         else
         if k < min2 then 
              min2 := k;
      end;

      if (max1 > 0) and (min1*min2 > max2*max3) then
         writeln(max1, ' * ', min1, ' * ', min2)
      else
      begin
         write(max1, ' * ', max2, ' * ', max3); 
          pr:=max1*max3*max2;
          write (' = ',pr);
      
      close(input);
      close(output);
      end;
end.

[Stilet]

Если я правильно понял то нет тут никакого массива... А сам алгоритм прост: Есть три переменные. Берется первое число. Если оно больше чем первая переменная, то значение первой переменной переходит во вторую переменную, а перед этом значение второй переходит в третью, сохраняя а-ля стеком данные. И так для каждой переменной. После чего число попадает в первую (или вторую смотря какая переменка сравнивается) переменную. Таким образом:

Число 1М 2М 3М
  1      0    0   0
  2      2    0   0
  3      3    2   0
  8      8    3   2
  4      8    4   3
  6      8    6   4

Т.е. переменные как бы раздвигают свои значения. Если первая больше - раздвигается вторая, если вторая больше подвигается третья.

[SlavaSSU]

это решение неверно, если есть отр. элементы

[Stilet]

решение неверно, если есть отр. элементы

Почему не верно?

[VIK_aka_TOR]

Сообщение от Stilet

Почему не верно?

наверное имеется ввиду случай когда лучше взять 2 отрицательных числа и третье положительное (- на - дают +), чем 2 положительных (но больше) и одно отриц...

к примеру
-4 3 2 -9
по вашему принципу возьмет -4 3 2
но наиболее подходящий вариант -9 -4 3
или

-2 4 5 -9 -18 8
если брать по возрастанию только
8 5 4
хотя лучше было бы -18 -9 5

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

[Stilet]

VIK_aka_TOR

Нда, действительно... Школа по мне плачет. В плане математики...

[rrrFer]

Это не жадный алгоритм ИМХО.

Жадный алгоритм должен содержать какое-то предположение, на основе которого сокращается перебор и, соответственно, уменьшается сложность.

Тут я ничего такого не вижу.

[VIK_aka_TOR]

к примеру можно отсортировать массив по убыванию
и затем уже смотреть, что больше
произведение первый трех (когда там все положительные), или первого и последних двух (положительное и два отрицательных)

[BDA]

VIK_aka_TOR, если смотреть именно на такие произведения, то именно они и рассматриваются в исходном коде, но без сортировки массива.

[VIK_aka_TOR]

Сообщение от BDA

VIK_aka_TOR, если смотреть именно на такие произведения, то именно они и рассматриваются в исходном коде, но без сортировки массива.

ну если сортировать, то и код меньше будет... и думаю быстродействие более менее (тут уже смотря какую сортировку взять)... ну а по правильности думаю будет норм... если чисел будет больше 3 )