Editing 0680 - K Split

== Enunț ==
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 și precizări ==

* 2 ≤ N ≤ 100 000
* elementele șirului A sunt numere întregi nenule din intervalul [-1 000 000, 1 000 000]

== Exemplu: ==
'''ksplitin.txt'''

4

2 3 -1 5

'''ksplitout.txt'''

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.

== Rezolvare ==
<syntaxhighlight lang="python">
import sys

NMax = 100003

def validate_input(n, a):
    if not (2 <= n <= 100000) or len(a) != n + 1 or any(not (-1000000 <= ai <= 1000000) for ai in a[1:]):
        print("Input invalid. Vă rugăm să verificați restricțiile.")
        return False
    return True

def ssm_st_dr(smax, poz, semn):
    smax[1] = a[1]
    poz[1] = 1
    for i in range(2, n + 1):
        if semn * smax[i - 1] >= 0:
            smax[i] = a[i] + smax[i - 1]
            poz[i] = poz[i - 1]
        else:
            smax[i] = a[i]
            poz[i] = i

def ssm_dr_st(smax, poz, semn):
    smax[n - 1] = a[n]
    poz[n - 1] = n
    for i in range(n - 2, 0, -1):
        if semn * smax[i + 1] >= 0:
            smax[i] = a[i + 1] + smax[i + 1]
            poz[i] = poz[i + 1]
        else:
            smax[i] = a[i + 1]
            poz[i] = i + 1

def sol(smax, smin, pozM, pozm, semn):
    global Max, Lmax
    for i in range(1, n):
        x = semn * (smax[i] - smin[i])
        if x > Max:
            Max = x
            Lmax = semn * (pozM[i] - pozm[i])

if __name__ == "__main__":
    sys.stdin = open("ksplitin.txt", "r")
    sys.stdout = open("ksplitout.txt", "w")

    n = int(input())
    a = [0] + list(map(int, input().split()))

    if not validate_input(n, a):
        sys.exit(1)

    Max = -float('inf')
    smax = [0] * NMax
    smin = [0] * NMax
    pozM = [0] * NMax
    pozm = [0] * NMax

    ssm_st_dr(smax, pozM, 1)
    ssm_dr_st(smin, pozm, -1)
    sol(smax, smin, pozm, pozM, 1)

    ssm_st_dr(smax, pozM, -1)
    ssm_dr_st(smin, pozm, 1)
    sol(smax, smin, pozM, pozm, -1)

    print(f"{Max}\n{Lmax + 1}")
</syntaxhighlight>