[C++] Zadanie "Taśma"

Rozwiązuję zadanie z MAIN2 pt."Taśma".
Program działa bez zarzutu przy małych liczbach,
jednak przy dużym "zestawie danych" za długo pracuje,
tzn. przy sprawdzaniu przez system sprawdzający wyrzuca:
"Przekroczenie limitu czasu"... (o 10ms-60ms)

Jak ten program można zoptymalizować lub zmienić?

Mój kod:


Treść zadania:

(Dostępna pamięć: 256 MB.) 6–12.12.2014 "Taśma" Jaś przypadkowo znalazł w domu bardzo długą taśmę. Bez chwili namysłu napisał na taśmie pewien ciąg liczb całkowitych dodatnich. Teraz chciałby znaleźć w tym ciągu dwie najdalej od siebie położone różne liczby. Zakładamy, że odległość między sąsiednimi liczbami to 1, między liczbami posiadającymi wspólnego sąsiada to 2 itd. Wejście Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą "n" (1≤n≤500000), oznaczającą długość sekwencji liczb zapisanej przez Jasia na taśmie. Drugi wiersz zawiera ciąg "n" liczb całkowitych ai(1≤ai≤1000000000), oddzielonych spacjami. Wyjście Jeżeli w podanym na wejściu ciągu nie ma żadnej pary różnych liczb, to "i"-ty wiersz powinien zawierać jedno słowo „BRAK”. W przeciwnym przypadku w "i-tym" wierszu powinna znajdować się jedna liczba całkowita, równa odległości między najdalszą parą różnych liczb w ciągu. __________________________________________________________ Przykład Dla danych wejściowych: 8 2 5 4 7 3 4 5 2 poprawnym wynikiem jest: 6 Wyjaśnienie do przykładu: Najdalszymi różnymi liczbami w sekwencji są m.in. pierwsza (czyli 2) i siódma (czyli 5). Natomiast dla danych wejściowych: 3 7 7 7 poprawnym wynikiem jest: BRAK

Wcześniej omawiane kwestie:

zawiesza się - zwraca komunikat bool przesuniecia[ d ];  po tej operacji czy na petli while "Program działa bez zarzutu"... Wiem, że ten działanie jest złe, ale nie znam się jeszcze na dynamicznej alokacji, więc tak zostało z mojej "zieloności".

jak rozumiesz optymalizację programu ? Zrobienie coś z nim by zwrócił on prawidłowy wynik w krótszym czasie.

//EDIT: (drobne podpowiedzi dostałem)

hm, ciężko coś poradzić nie mówiąc rozwiązania od razu, bo rozwiązanie jest generalnie bardzo proste... tylko wymaga jednej obserwacji generalnie trzeba zauważyć, że jedna liczba z tej wynikowej pary będzie "jakaś szczególna"

Użyj i/o z C, a nie C++.

tak się nie tworzy tablic.


możesz użyć vectora.

czemu tablicy nie przekazujesz przez wskaźnik i długości sekwencji przez referencje?

Użyj i/o z C, a nie C++.

???

tak się nie tworzy tablic.

Wcześniej omawiane kwestie: Wiem, że te działanie jest złe, ale nie znam się jeszcze na dynamicznej alokacji, więc tak zostało z mojej "zieloności".

możesz użyć vectora.

Zobaczę co da się z tym zrobić.

czemu tablicy nie przekazujesz przez wskaźnik

A noż nie umiem...

i długości sekwencji przez referencje?

Ma to jakieś znaczenie przy "inline"?

//EDIT:

Modyfikator register  "daje do zrozumienia" kompilatorowi, że zależy nam na szybkim dostępie do zmiennej, gdyż będziemy jej używać dużo razy i należy ją umieścić w rejestrze procesora. Nie możemy się odwoływać do zmiennej z modyfikatorem register o jej adres. Rejestr nie jest adresem pamięci, gdy usilnie próbujemy dowiadywać się jednak o jej adres, kompilator umieści zmienną w pamięci (gdzie może nam podać adres).

Moje pytanie jest takie:
Jak przy zagnieżdżonych pętlach
wyjść z nich wszystkich na raz?

Zmień algorytm. O(N^2) to za dużo. Wygląda, że łatwo to zrobić w O(2N)

Zmień algorytm. O(N^2) to za dużo.

Tyle obliczeń wykona tylko wtedy kiedy są wszystkie sobie równe...
Można by więc na początku sprawdzić czy wszystkie sobie są równe?

Wygląda, że łatwo to zrobić w O(2N)

Właśnie nie mam żadnej innej
koncepcji jak to łatwo wykonać. :C

"Jak przy zagnieżdżonych pętlach
wyjść z nich wszystkich na raz?"

goto jest dobrym rozwiązaniem lub return jeżeli jesteś w funkcji jakiejś

Tyle obliczeń wykona tylko wtedy kiedy są wszystkie sobie równe... Można by więc na początku sprawdzić czy wszystkie sobie są równe?

Ile wykona? O(N^2)? To jest złożoność a nie wzór na ilość wykonań. Poczytaj co oznacza złożoność.
Mówiąc prościej: kiedy nie są sobie równe i tak wykona dużo.

Właśnie nie mam żadnej innej koncepcji jak to łatwo wykonać. :C

Czyli nie masz żadnej koncepcji, teraz robisz to siłowo sprawdzając wszystkie kombinacje. W tych zadaniach nie chodzi o to, aby zakodować coś, ale aby wymyślić algorytm. Jak ktoś Ci poda rozwiązanie, to nic z tego zadania. Sama złożoność już tutaj jest dużą podpowiedzią. Pomyśl jak wykonać to zadanie tylko dwa razy przeglądając tablicę.

//

goto jest dobrym rozwiązaniem

Oczywiście, że nie jest. Pętlą sterujemy przez , ,  oraz dobrze skonstruowany warunek pętli.