Maksymalna suma spójnego fragmentu (algorytm Kadane'a)

Zadanie 10 z 10 · rozdział 24Trudność: 2 z 3listkadanedpfragment

Treść zadania

Otrzymujesz listę liczb całkowitych. Znajdź niepusty spójny fragment listy (kolejne elementy od indeksu p do indeksu k włącznie, $p \le k$) o największej sumie. Wypisz tę sumę oraz indeksy początku i końca fragmentu.

  • Jeśli kilka fragmentów ma tę samą, największą sumę — wybierz ten o najmniejszym indeksie początku p, a jeśli nadal jest remis — najkrótszy (o najmniejszym k).
  • Fragment musi mieć co najmniej jeden element, więc gdy wszystkie liczby są ujemne, wynikiem jest największa z nich (pierwsze jej wystąpienie).

Dane wejściowe

  • 1. linia: n — długość listy
  • 2. linia: n liczb całkowitych oddzielonych spacjami

Dane wyjściowe

  • 1. linia: największa suma
  • 2. linia: dwie liczby p k oddzielone spacją — indeksy (liczone od 0) pierwszego i ostatniego elementu fragmentu

Ograniczenia

  • $1 \le n \le 10^5$
  • elementy listy są z przedziału $[-10^4, 10^4]$

Uwagi

  • Sprawdzanie wszystkich fragmentów to około $n^2/2$ par (p, k) — przy $n = 10^5$ to miliardy działań. Algorytm Kadane'a robi to w jednym przejściu, w czasie $O(n)$: idąc po liście, pamiętaj sumę najlepszego fragmentu kończącego się na bieżącym elemencie oraz jego początek. Jeśli ta suma przed dołożeniem nowego elementu jest ujemna, opłaca się zacząć nowy fragment od bieżącego elementu; w przeciwnym razie przedłużasz dotychczasowy.
  • Remisy rozstrzygną się zgodnie z treścią, jeśli nowy fragment zaczniesz tylko przy sumie ściśle ujemnej (przy sumie 0 przedłużaj — początek zostaje wcześniejszy), a najlepszy wynik zmienisz tylko na ściśle większy.

Przykłady

Wejście
9
-2 1 -3 4 -1 2 1 -5 4
Wyjście
6
3 6

Fragment od indeksu 3 do 6: $4 + (-1) + 2 + 1 = 6$.

Wejście
5
4 -4 1 3 -1
Wyjście
4
0 0

Sumę 4 mają fragmenty 0..0, 0..3 i 2..3. Najwcześniej zaczynają się dwa pierwsze, a z nich krótszy jest 0..0.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 24

Trudniejsze zadania na listach: przekształcenia w miejscu, sumy prefiksowe, kopiec i programowanie dynamiczne. Liczy się nie tylko poprawny wynik, ale też dobry algorytm — w testach są także długie listy, na których rozwiązanie „sprawdzające wszystkie możliwości” nie zdąży się wykonać.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Lista liczb jest podawana w dwóch liniach: w pierwszej jest liczba elementów n, w drugiej n liczb całkowitych oddzielonych spacjami (o ile zadanie nie mówi inaczej).
  • Listę wynikową wypisuj w jednej linii, a jej elementy oddzielaj pojedynczą spacją (o ile zadanie nie mówi inaczej).
  • Indeksy liczymy od 0.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
-5
Oczekiwane wyjście
-5
0 0

Test 2

Nie uruchomiono
Wejście
1
7
Oczekiwane wyjście
7
0 0

Test 3

Nie uruchomiono
Wejście
4
-3 -1 -2 -1
Oczekiwane wyjście
-1
1 1

Test 4

Nie uruchomiono
Wejście
3
5 -5 5
Oczekiwane wyjście
5
0 0

Test 5

Nie uruchomiono
Wejście
4
0 0 0 0
Oczekiwane wyjście
0
0 0

Test 6

Nie uruchomiono
Wejście
3
-1 0 2
Oczekiwane wyjście
2
1 2

Test 7

Nie uruchomiono
Wejście
5
2 -1 2 -10 3
Oczekiwane wyjście
3
0 2

Test 8

Nie uruchomiono
Wejście
6
1 2 3 4 5 6
Oczekiwane wyjście
21
0 5

Test 9

Nie uruchomiono
Wejście
5
-1 3 -3 3 -1
Oczekiwane wyjście
3
1 1

Test 10

Nie uruchomiono
Wejście
400
-74 76 39 46 93 -62 52 57 -29 -13 94 42 -9 -9 -2 -80 -63 -61 74 -83 47 76 -70 66 89 33 54 27 -98 -10 -49 -55 -90 76 75 45 24 51 41 -86 -7 40 0 65 -92 32 56 22 78 -80 15 -58 -8 19 8 -42 -98 30 36 99 -14 35 -75 68 46 35 8 -91 -25 78 -59 74 -52 38 65 -10 -8 -24 1 76 6 1 65 6 42 -76 -5 4 -91 4 33 -27 56 83 74 -13 -42 -36 38 92 -68 -74 49 -62 -95 98 51 -18 -61 39 32 -13 -21 90 47 10 -84 -49 -7 43 3 23 -28 57 -72 -80 62 -37 78 -56 3 -63 9 -43 16 -66 -44 -1 94 -42 -3 -34 37 36 -48 -43 92 38 33 83 -6 10 -64 -96 -43 -64 -28 68 6 15 -98 79 9 19 94 78 -26 28 -78 -80 84 96 -18 -2 66 -70 5 92 -71 -68 -55 99 -39 -53 45 -80 -88 -41 -25 -38 -12 -93 -50 -87 64 -9 -84 -52 50 90 -83 58 -35 43 -76 10 80 -13 49 -29 -71 -50 30 70 -20 53 2 -78 -68 -59 49 86 99 42 -22 -55 -13 -9 33 8 55 48 84 20 38 3 8 77 -6 40 -88 -70 95 -42 25 18 45 47 -67 90 43 -60 6 -55 -87 -24 52 -71 -8 -32 -81 -11 70 -69 27 0 -56 54 -19 1 -56 60 -7 50 -56 39 -20 -8 53 -45 -68 -79 -13 39 -74 -42 -56 74 -55 25 -14 38 -51 -81 -43 -51 44 73 -74 -28 -91 48 39 -65 -9 -67 22 20 -54 -92 -37 89 -33 14 43 -89 1 -30 60 -70 35 -6 97 -59 -32 4 -25 95 51 -99 -51 72 43 80 72 88 81 18 -10 56 68 6 6 -89 57 22 14 -73 53 -33 -3 73 -76 -24 22 57 -8 -87 67 -2 16 -57 -93 18 -90 21 -27 -34 -44 69 31 8 43 -34 -78 -79 36 -7 -59 -39 -76 16 -85 51 -81 96 72 -61 84 -1 -50 6 1 -38 31 -35 -84 -96 89 22
Oczekiwane wyjście
907
1 115
Uruchom z własnymi danymi