Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_23_06 - Parzyste, nieparzyste II

Znajdź największą sumę podciągu w ciągu liczb całkowitych o następujących własnościach:

  • musi być spójny
  • jeśli będziemy przechodzić po wyrazach od lewej srony do prawej to suma napotkanych do danego momentu liczb nieparzystych musi być zawsze nie mniejsza niż suma napotkanych do tego momentu liczb parzystych
  • to samo dotyczy przejścia z prawej do lewej strony tego samego podciągu
  • szukany podciąg musi zaczynać się i kończyć liczbą nieparzystą
  • dopóki nie napotkamy liczby parzystej, to każda nieparzysta dodatnia, ujemna, czy też ich suma, będzie zawsze większa od nieokreślonej do tej pory sumy liczb parzystycc

Wejście

W pierwszym wierszu liczba określająca liczbę zestawów danych (nie więcej niż 1000).

Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu jedna liczba określająca długość ciągu (nie wiecej niż 100 000). W drugim wierszu kolejne liczby ciągu będące liczbami całkowitymi, gdzie każda z nich mieści się w przedziale [-106... 106]. 

Wyjście

Dla każdego zestawu jedna liczba określająca największą taką sumę. Gdy w ciągu nie ma liczb nieparzystych to wypisujemy 0.

Przykład

Wejście:
3
5
1 3 4 6 3
7
2 5 4 5 3 4 5
15
-3 -3 5 5 4 0 3 -4 -1 -2 2 -3 4 -3 -1
Wyjście:
4
26
12

Dodane przez:Marcin Kasprowicz
Data dodania:2015-06-03
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.