Fişierul intrare/ieşire:ksplit.in, ksplit.outSursăLot Vaslui 2014 - Baraj 4 Juniori
AutorEugen NodeaAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.07 secLimită de memorie10240 kbytes
Scorul tăuN/ADificultateN/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: Ai, Ai+1, …, Aj cu 1 ≤ i < j ≤ N. Prin lungimea secvenţei înţelegem numărul de elemente care o compun.

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

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 Ai, Ai+1, …, Aj 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 ≤ 105
  • elementele şirului A sunt numere întregi nenule din intervalul [-106, 106]

Exemplu

ksplit.inksplit.out
4
2 3 -1 5
6
3

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, Dmax = |5 – (-1)| = 6, Lmax = 3.
Se observă că există şi secvenţa -1 5 pentru care: s1 = -1, s2 = 5, Dmax = |-1 – 5| = 6 dar această secvenţă are lungimea 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?