1804 - ursulet

Sursa: 1804 - ursulet

---

Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transporta cu maşina ei de-a lungul zonelor în care acesta acumulează oboseală maximă.

Cerinţa

Să se determine zonele în care Lupita îl transportă pe ursuleţul Grizzlyuță.

Date de intrare

Fișierul de intrare ursulet.in conține pe prima linie numărul N, ce semnifică numărul de zone traversate de ursuleţ. Pe linia următoare se află N numere întregi, altitudinile zonelor.

Date de ieșire

Fișierul de ieșire ursulet.out va conține pe prima linie un număr întreg ce semnifică oboseală maximă acumulată de ursuleţ pe o porţiune de zone consecutive. Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță.

Restricţii şi precizări

• 1 ≤ n ≤ 100.000
• -1000 ≤ a ≤ 1000, a fiind altitudinea unei zone
• Dacă există mai multe subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă.ă cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător

Exemplu

Intrare

6

-5 0 3 1 -4 2

Ieșire

4

2 4

Rezolvare

Rezolvare ver. 1

# 1804 - ursulet

def read_input():
    n = int(input())
    altitudes = list(map(int, input().split()))
    return altitudes

def find_maximum_subarray(altitudes):
    max_sum = float('-inf')
    current_sum = 0
    start_index = 0
    end_index = -1
    current_start_index = 0

    for i in range(len(altitudes)):
        current_sum += altitudes[i]

        if current_sum > max_sum:
            max_sum = current_sum
            start_index = current_start_index
            end_index = i

        if current_sum < 0:
            current_sum = 0
            current_start_index = i + 1

    return max_sum, start_index, end_index

def write_output(result):
    max_sum, start_index, end_index = result
    with open('ursulet.out', 'w') as f:
        f.write(str(max_sum) + '\n')
        f.write(str(start_index + 1) + ' ' + str(end_index + 1) + '\n')

if __name__ == '__main__':
    altitudes = read_input()
    result = find_maximum_subarray(altitudes)
    write_output(result)

Explicatie Rezolvare

Pentru a rezolva această problemă, putem utiliza o metodă numită "maximum subarray problem", care constă în găsirea subsecvenței continue a unui șir dat, care are cea mai mare sumă. Putem utiliza o variantă a algoritmului Kadane, care funcționează în timp liniar.