Strona główna » Algorytmy » Artykuły » Największa suma podlisty listy
 

Największa suma podlisty listy

https://mattomatti.com/a0007

Algorytm

Największa suma podlisty listy jest zadanie, które polega na zsumowaniu k kolejnych elementów, aby otrzymać jak największą sumę. Na liście znajduje się zarówno liczby dodatnie jak i ujemne. Zadanie można rozwiązać algorytmem naiwnym, który sprawdzi wszystkie poprawne podlisty. Istnieje jednak algorytm Kadanego, który znacząco przyśpiesza proces.

Przykłady

Przykładowo dla listy L := {1, -2, 3, 1, 5} największą sumą podlisty jest suma elementów podlisty {3, 1, 5} = 9.

Warto jednak zauważyć, że w przypadku, że gdyby na pierwszej pozycji była wartość > 2 to największa wartość powstałaby poprzez zsumowanie wszystkich elementów. Przykładowo, gdy L := {8, -2, 3, 1, 5} to największa suma elementów podlisty wynosi już nie 9, a 15.

Poszukiwania naiwne

Dla listy o długości n podczas szukania naiwnego najpierw należałoby zsumować wszystkie elementy, a następnie zmniejszać długość podlisty o 1 i ponownie zsumować wszystkich podlist o długości n - 1. Oznacza to, że łącznie podlist będzie 1 + 2 + .. + (n - 1) + n = 0.5·(n + 1)·n = 0.5·(n2 + n). Oznacza to, że złożoność obliczeniowa wynosi Θ(n2). Poniżej został zamieszczony kod realizujący to zadanie:

Kod

C++
C#
  1. int maxSubList(int* lista, int n) {
  2.   int max = lista[0];
  3.   int suma;
  4.   for (int i = n; i >= 1; i--) {
  5.     for (int j = 0; j <= n - i; j++) {
  6.       suma = 0;
  7.       for (int k = 0; k < i; k++) {
  8.         suma += lista[k + j];
  9.       }
  10.       if (suma > max) {
  11.         max = suma;
  12.       }
  13.     }
  14.   }
  15.   return max;
  16. }

(1.) Funkcja przyjmuje dwa argumenty: lista - lista liczb całkowitych oraz n - długość listy. (2.) Początkowo należy przyjąć, że maksymalna suma wynosi tyle co pierwszy element. (3.) Zadeklaruj zmienną suma, która będzie używana podczas sumowania wybranej podlisty. (4.) Dla każdej długości podlisty: (5.) Dla każdej podlisty o długości i: (6.) zresetuj suma i (7. - 9.) zsumuj elementy tej podlisty, a następnie (10.) sprawdź czy nowa suma jest większa od dotychczas znalezionego maksimum. Jeśli tak to (11.) zastąp tę wartość. Po wykonaniu wszystkich pętli należy zwrócić (15.) wartość zmiennej max.

Algorytm Kadanego

Algorytm Kadanego to bardzo sprytne zauważenie prawidłowości zachodzących podczas sumowania kolejnych elementów. Przede wszystkim lista L := {1, -2, 3, 1, 5} jest równoważna w przypadku szukania maksymalnej sumy elementów podlisty L' := {1, -2, 9}. Algorytm rozpoczyna sumowanie od pierwszego elementu. Następnie do aktualnej sumy dodaje następny element z listy. W przypadku, gdy suma spadnie poniżej zera to algorytm zeruje sume. Jednak w przypadku, gdy suma jest dodatnia to należy sprawdzić czy nie jest większa od dotychczasowego maksimum. Za początkowe maksimum można przyjąć pierwszy element.

Złożoność obliczeniowa tego algorytmu to Θ(n), ponieważ każdy element jest pobierany i dodawany dokładnie jeden raz.

Przykład 1

Przykładowo dla L' := {1, -2, 9} algorytm kolejno wykona:

MaksimumSumai-ty elementKomentarz
101snowa = 1, nie jest większa od maksimum
11-1snowa = -1, jest mniejsza od zera, więc suma jest resetowana na 0
109snowa = 9, jest większa od maksimum, więc zostaje ustalone nowe maksimum

W podanym przykładzie największa suma podlisty wynosi 9.

Przykład 2

Warto rozważyć jeszcze jeden przypadek, który pokaże, że algorytm uwzględnia w sumie wartości ujemne, a nie szuka tylko maksimum wśród podlist złożonych z samych liczb dodatnich.

Przykładowo dla L' := {2, -1, 3, -2, -5, 1} algorytm kolejno wykona:

MaksimumSumai-ty elementKomentarz
202snowa = 2, nie jest większa od maksimum
22-1snowa = 1, nie jest większa od maksimum
213snowa = 4, jest to nowa wartość maksimum
44-2snowa = 2, nie jest większa od maksimum
42-5snowa = -3, jest mniejsza od zera, więc suma jest resetowana na 0
401snowa = 1, nie jest większa od maksimum

W podanym przykładzie największa suma podlisty wynosi 4.

Kod

C++
C#
  1. int maxSubList(int* lista, int n) {
  2.   int max = lista[0], suma = 0;
  3.   for (int i = 0; i < n; i++) {
  4.     suma = suma + lista[i];
  5.     if (suma > max) {
  6.       max = suma;
  7.     }
  8.     if (suma < 0) {
  9.       suma = 0;
  10.     }
  11.   }
  12.   return max;
  13. }

(2.) Przyjmij za maksimum 0 i wyzeruj początkową sumę elementów. (3.) Dla każdego elementu listy: (4.) wylicz nową sumę i (5.) sprawdź czy nowa suma jest większa od maksimum. Jeśli tak to (6.) zmień wartość maksimum. Następnie (8.) sprawdź czy nowa suma jest mniejsza od zera. Jeśli tak to (9.) wyzeruj sumę. Ten fragment kodu "wybiera", które podlisty złożone z samych liczb dodatnich zsumować pomimo ujemnych elementów pomiędzy nimi.

Testowanie funkcji

W celu przetestowania działania funkcji można skorzystać z funkcji maxSubListTEST(), która przyjmuje te same argumenty co funkcja maxSubList(). Funkcja ta wypisuje na ekranie komunikaty zrozumiałe dla programisty.

C++
C#
  1. void maxSubListTEST(int* lista, int n) {
  2.   if (n <= 0)
  3.     return;
  4.   cout << "Maksymalna suma podlisty {" << lista[0];
  5.   for (int i = 1; i < n; i++) {
  6.     cout << ", " << lista[i];
  7.   }
  8.   cout << "} wynosi " << maxSubList(lista, n);
  9.   cout << endl;
  10. }

Wykorzystanie funkcji maxSubListTEST() prezentuje poniższy kod:

C++
C#
  1. int main () {
  2.   int n = 5;
  3.   int listA[] = { 1, -2, 3, 1, 5 };
  4.   int listB[] = { 8, -2, 3, 1, 5 };
  5.   maxSubListTEST(listA, n);
  6.   maxSubListTEST(listB, n);
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz funkcję, która znajdzie minimalną wartość sumy elementów na podanej liście o długości n. Przyjmuje, że pod lista to kolejne k elementy z listy. Nagłówek funkcji powinien być następujący: int minSubList(int* lista, int n).

Przykładowo dla listy L:={-1, -2, 3, -3, -5} minimalna suma elementów wybranej podlisty wynosi -8.