@Norbert: max4: 1000, tak jak napisał Łukasz, max18: 675103
@Łukasz: dalej nie wiem, jaki jest Twój algorytm. W sumie nie wiem nawet w końcu, co rozumiesz poprzez stawianie granic. Ja idę w prawo od początku i gdy zejdzie mi suma poniżej zera (czyli liczba p < j), to tutaj stawiam tę granicę, od tego miejsca zaczynam od nowa i lecę dalej na prawo. Mam więc najdłuższe fragmenty, które są ok w prawo. Teraz dla tych fragmentów sprawdzam, je analogicznie w lewo i ew. dostawiam granice. I tak w kółko dopóki cały fragment nie jest dobry w dwie strony. Też to mam rekurencyjnie zrobione.

Dzięki - brut gdzieś leży na dysku mojego komputera, jednakże jestem w terenie i nie mam do niego dostępu ;-)

@Nobert 1000, chociaż nie wiem, czemu nie zaklepałeś bruta, żeby sprawdzić
@Grzegorz Graczyk Masz całkowicie inny sposób działania niż zwykłe stawianie granic, więc nie wiem czy to heura czy wzorcówa
@Jakub Cisło Ja mam zrealizowane stawianie granic poprzez fcja rekurencyjna szukająca najlepszego wyniku na danym przedziale.Błędnie założyłem, że trudność przykładu zależy od głębokości stosu rekurencyjnego, jednakże jest inaczej.

@Jakub: Czy możesz powiedzieć jaki jest out dla testu z Twojego przedostatniego wpisu? :-)

To opiszcie dokładniej co robicie patrząc w lewo i prawo, chętnie się dowiem :)

Nie wiem jak twój algorytm, ale mojemu wystarczyło 2 RAZY przejechać po tym przykładzie czyli tyle samo co w pierwszym poście. Również myślałem o testach takiej budowy, ale one akurat nie są jakieś trudne, bo zawsze wystarczą dla nich dwa obroty pętlą w tą i wewte.
// edit
Wcale nie tak łatwo jest z tymi testami :P

Ja też napisałem taki algorytm, który patrzy na przemian w prawo i lewo, jednak można skonstruować przykład, w którym musimy powtórzyć tą czynność O(sqrt(n)) razy. Zasada generowania jest całkiem prosta, poniżej mały przykład:
193
pppppppppppppjjjjjjjjjjjjpppppppppppjjjjjjjjjjpppppppppjjjjjjjjpppppppjjjjjjpppppjjjjpppjjpjjjppppjjjjjppppppjjjjjjjppppppppjjjjjjjjjppppppppppjjjjjjjjjjjppppppppppppjjjjjjjjjjjjjpppppppppppppp
(13p 12j 11p 10j 9p 8j 7p 6j 5p 4j 3p 2j 1p 3j 4p 5j 6p 7j 8p 9j 10p 11j 12p 13j 14p)
Duży przykład: http://cubix.one.pl/public/max4.in
Ja dodałem optymalizację, że zamieniam np. pppppjjppp -> 5 2 3. Tak nowo powstały ciąg jest długości O(sqrt(n)) dla powyższych testów, więc całość ma złożoność O(n). Dla takiej optymalizacji maxtest poniżej, na oitimetoolu czas miałem ok 1,3 s, jednak złożonościowo jest to chyba O(n sqrt(n)) z dość małą stałą:
http://cubix.one.pl/public/max18.in

DOBRZE!!! Nauczyłeś pokory conajmniej 2 osób. ;]

W c++ nie trzeba jawnie zwracać 0. ;-)

C++ Standard, chapter 3.6.1 paragraph 5:

A return statement in main has the effect of leaving the main function (destroying any objects with auto- matic storage duration) and calling exit with the return value as the argument. If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

Wydaje mi się, że zapomniałeś chyba o zwróceniu 0 na końcu programu :)

To chętnie poznam test, który zepsuje ten kod: http://ideone.com/cnNf55 ;-)

eeee... Nie?

Ależ Wy tu kombinujecie. A nie da się tego zadania zrobić jednym przejściem po całym ciągu bawiąc się jakimś stosem? :-)

Tak, ja zrobilem, mialem 1800 linii :D

Łukasz Wołoszyn, mam to rozwiązanie, które Cię ciekawi i wg moich wyliczeń opartych na obserwacjach, najgorszym możliwym przypadkiem może być nlog(n/2), ale nie potrafiłem takiego przykładu stworzyć i mój program podobnie jak Twój miał najgorszą złożoność na wszystkich testach z forum 6n.