Analiza

Praktično je u zadatku dat sortiran niz od ~N~ prirodnih brojeva i zahteva se promena najviše jednog člana tog niza tako da se minimizuje najveća razlika članova koji su susedni ne po indeksima, već po vrednostima.

Da bi se to postiglo, potrebno u jednom prolasku kroz niz odrediti najveću razliku između dva susedna člana. Ta najveća razlika može biti jedinstvena ili nejedinstvena, a može se pojavljivati na rubovima (početak i/ili kraj) niza i/ili u sredini niza.

Ukoliko se najveća razlika susednih članova niza pojavljuje na početku, odnosno na kraju niza, moguće je prostim izjednačavanjem prvog sa drugim članom niza, odnosno poslednjeg sa pretposlednjim članom u potpunosti eliminisati tu razliku.

Međutim, za razliku od unutrašnjih članova niza, pažljivom promenom rubnih članova ne može doći do povećanja maksimalne razlike. Ova činjenica može se iskoristiti za smanjenje još neke razlike unutar ili na drugom kraju niza. Naime, umesto izjednačavanja rubnog člana niza sa njegovim susedom, ovaj član se može iskoristiti za potiranje druge najveće razlike. Na taj način, praktično je u pojedinim slučajevima moguće eliminisati prve dve najveće razlike pod uslovom da se jedna od njih nalazi na rubu niza.

Konkretno, nije teško pokazati da se do optimalnog rešenja uvek dolazi promenom najmanjeg ili najvećeg člana niza. Od ova dva člana neophodno je izmeniti onaj čija je razlika s njegovim jedinim susedom veća. Izmenjena vrednost treba da umanji najveću razliku u ostatku niza, a to je ispravno učiniti promenom na vrednost aritmetičke sredine susednih članova niza među kojima je razlika najveća.

Smernice za algoritam

Može se prvo ispitati granični slučaj od dva člana koji se jednostavno rešava izjednačavanjem vrednosti bilo prvog člana sa drugim, bilo drugog sa prvim. Ukoliko se pak niz sastoji od tri i više članova treba odrediti da li je veća razlika između prvog i drugog ili pretposlednjeg i poslednjeg člana niza. Potom u jednom prolasku kroz ostatak niza (kome ne pripada rub niza sa većom razlikom) odrediti najveću razliku između susednih članova. Jednostavnom promenom vrednosti rubnog člana na vrednost aritmetičke sredine dva susedna člana s najvećom razlikom dolazimo do rešenja zadatka. Kako u zadatku imamo jedan prolazak kroz niz u kojoj se traži najveća razlika susednih članova složenosti ~\mathcal{O}(N)~, to je ukupna vremenska složenost algoritma linearna.