Jak w czasie O(N) znaleźć rozwiązanie zadania: mamy tablicę int'ów, znaleźć największą wartość A[i] + A[k] - (k - i) gdzie 0 <= i <= k < count(A) / czyli suma dwóch elementów pomniejszona o odległość między nimi.

#programowanie #algorytm
  • 8
  • Odpowiedz
  • Otrzymuj powiadomienia
    o nowych komentarzach

Ah, widzę że w pytaniu napisałeś 0<=i<=k<=cnt(A), czyli i może być równe k, wtedy bierzesz naturalnie największy element tablicy*2 :P


@echelon_: Ups. Błąd jest ale nie w tych warunkach, indeksy mogą być takie same, ale w definicji co wygrywa: odległość pomiędzy elementami jest premiowana, tzn. tam ma być plus nie minus: A[i] + A[k] + (k - i) / bo w przeciwnym wypadku masz rację, że byłoby to trywialne.
  • Odpowiedz