[dybligliniaczek]

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

[A.....k]

@dybligliniaczek: taktyk

[echelon_]

@dybligliniaczek: Jedna pętla, cztery zmienne tymczasowe przechowujące: wartość największą dla indeksów oraz same indeksy. Ta da!

edyta: Na końcu oczywiście samo wyliczenie wartości końcowej.

[dybligliniaczek]

@echelon_: być może, ale na końcu może się okazać że jeżeli od sumy tych dwóch największy odejmiemy różnicę indeksów to wyjdzie nam mniejsza liczba niżby wziąć sumę liczb trochę mniejszych ale bliżej siebie. Np. dane wejściowe: [1,7,8,2,3,-5,0,-1,9] / wg tego jak zrozumiałem twój opis wybrane by były 8 i 9 na indeksach 2 i 8 czyli wynik: 17 - 6 = 11

a lepszą parą jest 7 i 8 na indeksach

[F.....d]

@dybligliniaczek: Najpierw zacznijmy od prostego algorytmu kwadratowego:

idziemy do przodu. Niech k będzie indeksem na którym aktualnie jesteśmy. Teraz idziemy do tyłu(pętla w pętli), indeksy które po kolei sprawdzamy będą się nazywały i. Teraz szukamy największej A[i] + A[k] - (k - i), czyli A[i] + A[k] - k + i, czyli dla ustalonego k nasz wynik będzie największy wtedy, gdy największe będzie A[i] + i.

Ale zaraz! Po co iść

[F.....d]

@dybligliniaczek: 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

Zakładając, że jednak się tu pomyliłeś i chodziło o i

Teraz na Twoim przykładzie: A = [1,7,8,2,3,-5,0,-1,9]

Liczymy sobie opisaną przeze mnie tablicę pomocniczą, nazwijmy ją P.

P = [niezdefiniowane, 1, 8, 10, 10, 10, 10, 10, 10]. Zauważ, że elementy tablicy są ustawione w kolejności rosnącej, dlatego policzenie jej

[echelon_]

@dybligliniaczek: Piąta zmienna tymczasowa przechowująca wynik ostateczny. Ta da!

[dybligliniaczek]

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.

[F.....d]

@dybligliniaczek: I dalej jest, nic się nie zmieniło, sposób ten sam