Zadanie w programie Codewars: Maksymalna suma podtablicy
Problem podtablicy o maksymalnej sumie polega na znalezieniu maksymalnej sumy ciągłego podsekwencji w tablicy lub liście liczb całkowitych:
maxSequence({-2, 1, -3, 4, -1, 2, 1, -5, 4});
//should be 6: (4, -1, 2, 1}
Prosty przypadek jest wtedy, gdy lista składa się tylko z liczb dodatnich, a maksymalna suma jest sumą całej tablicy. Jeśli lista składa się tylko z liczb ujemnych, zamiast tego zwróć 0.
Uważa się, że pusta lista ma zerową największą sumę. Zauważ, że pusta lista lub tablica jest również prawidłową podlistą/podtablicą.
Problem podtablicy o maksymalnej sumie polega na znalezieniu maksymalnej sumy ciągłego podsekwencji w tablicy lub liście liczb całkowitych:
maxSequence({-2, 1, -3, 4, -1, 2, 1, -5, 4});
//should be 6: (4, -1, 2, 1}
Prosty przypadek jest wtedy, gdy lista składa się tylko z liczb dodatnich, a maksymalna suma jest sumą całej tablicy. Jeśli lista składa się tylko z liczb ujemnych, zamiast tego zwróć 0.
Uważa się, że pusta lista ma zerową największą sumę. Zauważ, że pusta lista lub tablica jest również prawidłową podlistą/podtablicą.
More Questions From This User See All
Odpowiedź:
Rozwiązanie w języku Python:
```python
def maxSequence(arr):
max_sum = 0
current_sum = 0
for num in arr:
current_sum += num
if current_sum < 0:
current_sum = 0
if current_sum > max_sum:
max_sum = current_sum
return max_sum
```
Funkcja `maxSequence` przyjmuje listę liczb całkowitych `arr` i zwraca maksymalną sumę ciągłej podtablicy. Algorytm działa w czasie liniowym O(n), gdzie n to długość listy.
Algorytm iteruje po liście i dla każdej liczby dodaje ją do bieżącej sumy `current_sum`. Jeśli `current_sum` jest mniejsze od zera, to ustawia je na zero, ponieważ nie ma sensu kontynuować sumowania, jeśli suma jest ujemna. Jeśli `current_sum` jest większe od `max_sum`, to aktualizuje wartość `max_sum`.
Na końcu funkcja zwraca wartość `max_sum`.