Niby dyszka wpadła, ale mam lekki niedosyt że algorytm jest mocno toporny...

1) Sprawdzam warunki brzegowe na NIE, typu: 0 w środku ciągu, element dużo większy od swoich sąsiadów itd
2) Próbuję rozpoznać, z jakim z 3 scenariuszy mam do czynienia:
a) wyliczanka zaczyna i kończy się w jednym punkcie - wtedy poza tym jednym punktem reszta powinna być ładnym cyklem, bez "wąskich gardeł" prowadzących tylko w jedną stronę
b) wyliczanka zaczyna i kończy się w różnych punktach (ale nie sąsiadujących) - wtedy poza cyklami mamy ścieżkę prowadzącą między tymi punktami
c) wyliczanka zaczyna i kończy się w sąsiadujących punktach - możemy zacząć gdziekolwiek i wszystko się zamknie w pełnym cyklu (bez ostatniej krawędzi)
3) każdy z tych scenariuszy ma osobny algorytm, ale zasadniczo sprowadza się do znajdowania i usuwania wszystkich sekwencji x->y y->x, aż zostanie nam jeden punkt (a), ścieżka (b) lub nic (c).

Ktoś ma ładniejszy algorytm i zechce się podzielić?

Wywalam przypadki gdzie ciąg nie jest spójny i puszczam takiego zachłana osobno dla indeksów startowych 0 oraz 1 (licząc od pierwszej niezerowej wartości): idź w lewo ile sie da, jak nie mogę to idź raz w prawo (i tak w kółko). Jak wyzeruję cały ciąg to odpowiedź to TAK, w przeciwnym wypadku NIE. Trzeba sprawdzić dwa indeksy bo jeżeli np. suma na nieparzystych indeksach jest większa, to trzeba od nich zacząć (ponieważ na przemian zmniejszamy wartości na nieparzystych i parzystych indeksach).
Dowodu poprawności nie mam, opierałem się bardziej na intuicji :P (no i oczywiście na testach z forum)

Może nie być ładniejszy, ale myślę że ma sensowną motywację:

Załóżmy prostszy wariant, że kończymy wyliczankę koło miejsca gdzie ją rozpoczęliśmy - mamy cykl. Żeby zweryfikować czy w takim wariancie wyliczanka jest poprawna, chcemy zobaczyć czy da się dać krawędzie skierowane między sąsiadującymi elementami, tak aby każdy miał odpowiednio dużo krawędzi wchodzących oraz istniał cykl eulera. Aby tak się dało, musi być >= 1 krawędź między każdą parą sąsiadującą oraz tyle samo krawędzi wchodzących do wierzchołka co wychodzących (w szczególności musi ich być dokładnie a_i dla i-tego elementu).

Wiemy, że z elementu 1 musi wychodzić do 2 a_1 krawędzi. Skoro do 2 wchodzi w sumie a_2 krawędzi to musi wychodzić z 2 do 3 a_2 - a_1 krawędzi. Analogicznie z 3 do 4 wychodzi a_3 - a_2 + a_1 krawędzi itd. Powiedzmy że z i -> i+1 wychodzi e_i krawędzi. Weryfikujemy czy ciąg e jest sensowny.

Jeżeli wyliczanka się nie zacykla, to znaczy że wystarczy dołożyć ścieżkę krawędzi (L -> L + 1 -> L + 2 -> . . . -> R) aby się zacyklała. Inaczej: wystarczy dołożyć ścieżkę krawędzi żeby ciąg e_1 . . . e_n był dobry. Dokładanie takiej ścieżki zmienia ciąg e w bardzo przewidywalny sposób (na zmianę dokłada +1 i -1 do elementów e na przedziale, pomijając jakieś przypadki brzegowe). Wystarczy zobaczyć czy istnieje przedział e, taki że zmieniając elementy na nim o +1, -1 na zmianę dostaniemy dobry ciąg.

Ja tak samo jak Antek tylko wyszło mi to z innej analizy. Jeśli da się skonstruować jakąkolwiek wyliczankę, to da się skonstruować wyliczankę postaci regexa (dla jakiegoś p): p p-1 ... 2 1 (2 1)+ 2 (3 2)+ 3 (4 3)+ ... n-1 (n n-1)+ n* (zakładając że wszystkie liczby są niezerowe).

Dowód wygląda w taki sposób, że patrzymy na wszystkie wystąpienia 1 i widzimy, że wszystkie z nich są otoczone przez 2 z którejś lub obu stron. Możemy teraz przenieść takie pary 1 2 do jednej z wybranych jedynek, uzyskując 1 2 1 2 ... 1 i wszystkie jedynki są w tym fragmencie. Logikę kontynuujemy teraz dla elementu 2, który poza tym blokiem jest już zawsze otoczony z jednej lub obu stron przez 3 - parę 2,3 przenosimy na koniec bloku 1212...1 (może się zdarzyć, że jednej 2 nie uda się sparować odpowiednio z 3, dlatego nasze rozwiązanie rośnie też w stronę początku w kierunku p, ale tylko o max jedno wystąpienie).

Dla każdego p oznaczamy przez k_i liczbę powtórzeń (i i+1) w regexie i otrzymujemy układ równań na liczbę wystąpień danej liczby w wyliczance: a_i = 1+k_i+k_(i-1)-1+[p>=i]. Te układy dla różnych p mają prawie identyczne rozwiązania modulo sufixowa operacja więc nie trzeba ich za każdym razem rozwiązywać od nowa (to jest ten sam układ co Antek opisał u siebie).