Mamy daną tablicę liczb całkowitych \(\displaystyle{ A \left[ n \right]}\) i interesuje nas znalezienie \(\displaystyle{ \max \left\{ |i-j|:i,j \in \left\{ 0,...,n-1\right\};A \left[ i \right] =A \left[ j \right] \right\}}\). Jedyny pomysł jaki mi przychodzi do głowy (który nei jest chamskim \(\displaystyle{ O \left( n^2 \right)}\) to użycie dodatkowej pamięci:
tablicę \(\displaystyle{ A}\) sortujemy quick-sortem (otrzymując tablicę \(\displaystyle{ A'}\) i jednocześnie tworzymy tablicę \(\displaystyle{ B \left[ n \right]}\) taka, ze \(\displaystyle{ B \left[ i \right]}\) koduje, z której komórki \(\displaystyle{ A}\) przyszedł element \(\displaystyle{ A' \left[ i \right]}\). Jednocześnie nic nie tracąc możemy założyć, że jeśli \(\displaystyle{ A' \left[ i \right] =A' \left[ j \right]}\) to \(\displaystyle{ B \left[ i \right] < B \left[ j \right]}\) dla \(\displaystyle{ i<j}\). No i wtedy już łatwo można liniowo znaleźć to maksimum, czyli ostatecznie pamięciowo jest to \(\displaystyle{ O \left( n \right)}\), a obliczeniowo \(\displaystyle{ O \left( n \cdot \ln \left( n \right) \right)}\). Da się to zrobić szybciej? (pod względem obliczeń)
