== include(page="template/taskheader" task_id="ksplit") ==
Poveste şi cerinţă...
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**.
h2. Cerinţă
Cunoscând $N$ şi valorile elementelor şirului $A$, să se determine **Dmax** şi **Lmax**:
h2. Date de intrare
Fişierul de intrare $ksplit.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $ksplit.out$ ...
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**.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 10^5^$
* elementele şirului $A$ sunt numere întregi nenule din intervalul $[-10^6^, 10^6^]$
h2. Exemplu
table(example). |_. ksplit.in |_. ksplit.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
2 3 -1 5
| 6
3
|
h3. 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$
== include(page="template/taskfooter" task_id="ksplit") ==
