Matematické Fórum

Ahoj,

mám vytvořit algoritmus, který najde v poli n vzájemně různých čísel x_1, x_2, ..., x_n optimální prvek.
Ke každému číslu je asociována hodnota w_1, w_2, .... w_n, taková, že platí



A pro ten optimální prvek má platit:





Výsledný algoritmus má mít složitost O(n). Zatím mám takovýto algoritmus, který ale není asi úplně korektní, jelikož bere prvky, které mají index i < k, ale ne x_i < x_k:

proc OptimalElement(arr[])
  prevs_w := 0
  nexts_w := 0
 
  for (i = 0; i <= n; i++)
  {
    wi := arr[i].w
   
    nexts_w := 1 - prevs_w - wi
 
    IF (prevs_w < 0,5 && nexts_w <= 0,5) THEN
      return arr[i]
    ELSE
      prevs_w := prevs_w + wi
    ENDIF
  }
end

Můžete mi poradit? Máte nějaký nápad?