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>