Fişierul intrare/ieşire:	ksplit.in, ksplit.out	Sursă	Lot Vaslui 2014 - Baraj 4 Juniori
Autor	Eugen Nodea	Adăugată de	Alexandru Valeanu •AlexandruValeanu
Timp execuţie pe test	0.035 sec	Limită de memorie	10240 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ksplit

Se consideră un şir A cu N elemente întregi nenule. Numim secvenţă a şirului A orice succesiune de elemente aflate pe poziţii consecutive în şir: A_i, A_i+1, …, A_j cu 1 ≤ i < j ≤ N. Prin lungimea secvenţei înţelegem numărul de elemente care o compun.

Pentru orice secvenţă A_i, A_i+1, …, A_j vom numi split-point un indice k, i ≤ k < j, care împarte secvenţa în două subsecvenţe nevide: A_i, A_i+1, …, A_k respectiv A_k+1, A_k+2, …, A_j.

Fie Dmax valoarea absolută maximă a diferenţei sumelor elementelor celor două subsecvenţe separate de un split-point, luând în considerare toate secvenţele A_i, A_i+1, …, A_j posibile şi fie Lmax lungimea maximă a unei secvenţe caracterizată de valoarea Dmax.

Cerinţă

Cunoscând N şi valorile elementelor şirului A, să se determine Dmax şi Lmax:

Date de intrare

Fişierul de intrare ksplit.in conţine pe prima linie un număr natural N ce reprezintă numărul de elemente al şirului A, iar pe cea de-a doua linie N numere întregi nenule despărţite prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire ksplit.out va avea două linii. Prima linie conţine numărul natural Dmax iar următoarea linie conţine numărul natural Lmax.

Restricţii

• 2 ≤ N ≤ 10⁵
• elementele şirului A sunt numere întregi nenule din intervalul [-10⁶, 10⁶]

Exemplu

Explicaţie

Dintre toate secvenţele ce se pot forma, se alege secvenţa 2 3 -1, care este formată din primele 3 elemente ale şirului.
Valoarea Dmax este 6, adică: s1 = 2 + 3 = 5, s2 = -1, D_max = |5 – (-1)| = 6, L_max = 3.
Se observă că există şi secvenţa -1 5 pentru care: s1 = -1, s2 = 5, D_max = |-1 – 5| = 6 dar această secvenţă are lungimea 2

Cum se trimit solutii?