Andrada378: Pagină nouă: == 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. Fi...

2024-01-03T14:33:04Z

Pagină nouă: == 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. Fi...

New page

== 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>

0680 - K Split - Revision history