@Jakub Cisło czyli dokładnie jak ja
@Filip Łubniewski Jest dowód na poprawność takiego algo, więc kontrprzykładu nie będzie, jednakże mam nadzieję, że sumy abs liczysz w stałym czasie :)
@Jan Góra przy tym sposobie tworzenia testów nie ma większego maxtesta

A co sądzicie o tym? Np. dla :
1 -2 5 -3 3 -1 1 -5 1
początkowo maxem, początkiem oraz końcem najlepszego ciągu jest element pierwszy z brzegu (ciąg czyszczę tak aby zawsze z przodu i na końcu znajdowała się liczba dodatnia), idąc w prawo sumuję kolejne elementy, jeśli suma jest równa/wieksza maxowi to przesuwam koniec ciągu na aktualnie dodawany do sumy element i nowym maxem jest suma. Jeśli suma zejdzie poniżej zera to sumuje abs wartości ciągu z zakresu początek-koniec i sprawdzam czy uzyskana suma jest większa od jakiegoś tam wcześniej ustalonego maxa2. Następnie powtarzam wszystko od nowa dla kolejnych elementów. Wypisuje max2. Może znajdzie ktoś kontrprzykład?

@Jakub wynik 675103 wydaje się być dość duży.. pewnie jest jeszcze jakiś większy maxtest?

@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?