Algorytmy i Struktury Danych - Podzbiór o największej sumie

Mamy ciąg liczb, np. {-4, 3, -1, 2}. Naszym zadaniem jest znalezienie sumy podciągu kolejnych elementów, która ma największą wartość. Rozdzielmy ten ciąg na podciągi kolejnych elementów (w tabelce oznaczone kolorem zielonym) i policzmy ich sumy:

Podciąg				Suma
-4	3	-1	2	-4
-4	3	-1	2	-1 = -4+3
-4	3	-1	2	-2 = -4+3 - 1
-4	3	-1	2	0 = -4+3 - 1+2
-4	3	-1	2	3
-4	3	-1	2	2 = 3 - 1
-4	3	-1	2	4 = 3 - 1+2
-4	3	-1	2	-1
-4	3	-1	2	1 = -1+2
-4	3	-1	2	2

Największą sumę posiada podciąg {3, -1, 2}. Suma ta wynosi 4.

do podrozdziału do strony

Największą sumę możemy znaleźć przez obliczenie wszystkich sum częściowych i wybranie spośród nich największej. Pierwszy algorytm będzie pracował wg tej właśnie zasady.

W algorytmie będziemy pamiętać:

Największą wartość sumy częściowej w zmiennej ms.
Bieżąco wyliczaną sumę częściową w zmiennej bs.
Indeksy startu i końca podciągu o bieżąco największej sumie w zmiennych ip oraz ik.

Zasada działania będzie następująca:

W algorytmie będą dwie pętle: pętla i będzie wybierała elementy startu podciągu, a wewnętrzna pętla j będzie wybierała kolejne elementy końca podciągu. W pętli wewnętrznej będzie obliczana suma bs kolejno elementów o indeksach od i do j. Jeśli suma bs okaże się większa od sumy maksymalnej ms, to do ms wpiszemy sumę bs i jednocześnie zapamiętamy pozycję startu i końca tego podciągu w zmiennych ip oraz ik. Gdy zewnętrzna pętla i zakończy działanie, w zmiennych ms, ip, ik znajdzie się wynik.

Algorytm znajdowania największej sumy podciągu

Wejście:

n : liczba elementów tablicy, n ∈ N.
T : tablica n-elementowa z ciągiem liczb, elementy są liczbami całkowitymi lub rzeczywistymi.

Wyjście:

ms : największa suma podciągu, typ taki sam jak typ elementów T.
ip : indeks pierwszego elementu podciągu, ip ∈ C.
ik : indeks ostatniego elementu podciągu, ik ∈ C.

Elementy pomocnicze:

i, j : przebiegają przez kolejne indeksy elementów T. i, j ∈ C.

Lista kroków:

K01: ms ← najmniejsza liczba ; ta wartość zostanie uaktualniona
K02: Dla i = 0, 1, …, n-1:      ; i wyznacza pierwszy element podciągu
     wykonuj kroki K03…K09
K03:   bs  ← 0               ; zerujemy sumę bieżącą
K04:   Dla j = i, i+1, …, n-1:  ; j wyznacza ostatni element podciągu
       wykonuj kroki K05…K09
K05:     bs  ← bs+T[j]     ; liczymy sumę częściową
K06:     Jeśli bs ≤ ms, 
         to następny obieg K04
K07:     ms  ← bs            ; uaktualniamy zmienne wynikowe
K08:     ip  ← i             ; indeks początku podciągu
K09:     ik  ← j             ; indeks końca podciągu
K10: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tworzy tablicę 20 elementową i wypełnia ją całkowitymi liczbami pseudolosowymi od -99 do 99. Następnie znajduje największą sumę podciągu oraz pozycję tego podciągu w tablicy.

Pascal

// Największa suma podciągu
// Algorytm prosty
// Data:   22.02.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

program prg;

const
  N = 20; // liczba elementów ciągu

// Procedura znajduje największą
// sumę podciągu algorytmem prostym
//---------------------------------
procedure maxSum(n : integer;
                 var T : array of integer;
                 var ms, ip, ik : integer);
// Elementy pomocnicze
var i, j, bs : integer;

begin
    ms := -2147483648; // Najmniejsza liczba integer
    for i := 0 to n-1 do
    begin
        bs := 0; // Bieżąca suma
        for j := i to n-1 do
        begin
            inc(bs, T[j]);
            if bs > ms then
            begin
                ms := bs; // Uaktualniamy
                ip := i;
                ik := j;
            end;
        end;
    end;
end;

// Procedura wypisuje zawartość tablicy
//-------------------------------------
procedure piszT(var T : array of integer;
                ip, ik : integer);
var i : integer;

begin
    for i := ip to ik do write(i:4);
    writeln;
    for i := ip to ik do write(T[i]:4);
    writeln;
    writeln;
end;

var
  T : array [0..N-1] of integer;
  i, ip, ik, ms : integer;

begin
    randomize;
    for i := 0 to N-1 do
        T[i] := -99+random(199);

    // Wyświetlamy cały ciąg
    piszT(T, 0, N-1);

    // Znajdujemy największą sumę podciągu
    maxSum(N, T, ms, ip, ik);

    // Wyświetlamy wyniki:
    writeln('ms = ', ms);
    writeln('ip = ', ip);
    writeln('ik = ', ik);
    writeln;
    piszT(T, ip, ik);
end.

C++

// Największa suma podciągu
// Algorytm prosty
// Data:   22.02.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

const int N = 20; // liczba elementów ciągu

// Funkcja znajduje największą
// sumę podciągu algorytmem prostym
//---------------------------------
void maxSum(int n, int T[], 
            int & ms, 
            int & ip, int & ik)
{
    // Elementy pomocnicze
    int i, j, bs;

    ms = INT_MIN; // Najmniejsza liczba INT
    for(i = 0; i < n; i++)
    {
        bs = 0; // Bieżąca suma
        for(j = i; j < n; j++)
        {
            bs += T[j];
            if(bs > ms)
            {
                ms = bs; // Uaktualniamy
                ip = i;
                ik = j;
            }
        }
    }
}

// Funkcja wypisuje zawartość tablicy
//-----------------------------------
void piszT(int T[], int ip, int ik)
{
    int i;
    for(i = ip; i <= ik; i++)
        cout << setw(4) << i;
    if(ik-ip < 19) cout << endl;
    for(i = ip; i <= ik; i++)
        cout << setw(4) << T[i];
    cout << endl << endl;
}

int main()
{
    int T[N], i, ip, ik, ms;

    srand(time(NULL));
    for(i = 0; i < N; i++)
        T[i] = -99+rand() % 199;
    // Wyświetlamy cały ciąg
    piszT(T, 0, N-1);

    // Znajdujemy największą sumę podciągu
    maxSum(N, T, ms, ip, ik);

    // Wyświetlamy wyniki:
    cout << "ms = " << ms << endl
         << "ip = " << ip << endl
         << "ik = " << ik << endl << endl;
    piszT(T, ip, ik);
    return 0;
}

Basic

' Największa suma podciągu
' Algorytm prosty
' Data:   22.02.2024
' (C)2024 mgr Jerzy Wałaszek
'---------------------------

const NN = 20 ' liczba elementów ciągu

' Funkcja znajduje największą
' sumę podciągu algorytmem prostym
'---------------------------------
sub maxSum(byval n as integer, _
           T() as integer, _
           byref ms as integer, _
           byref ip as integer, _
           byref ik as integer)

' Elementy pomocnicze
dim as integer i, j, bs

    ms = -2147483647 ' Najmniejsza liczba INT
    for i = 0 to n-1
        bs = 0 ' Bieżąca suma
        for j = i to n-1
            bs += T(j)
            if bs > ms then
                ms = bs ' Uaktualniamy
                ip = i
                ik = j
            end if
        next
    next
end sub

' Procedura wypisuje zawartość tablicy
'-----------------------------------
sub piszT(T() as integer, _
          ip as integer, _
          ik as integer)
   
    dim i as integer
    for i = ip to ik: print using "####"; i;: next
    print
    for i = ip to ik: print using "####"; T(i);: next
    print: print
end sub

dim as integer T(NN), i, ip, ik, ms

randomize
for i = 0 to NN-1
    T(i) = -99+int(rnd * 199)
next
   
' Wyświetlamy cały ciąg
piszT(T(), 0, NN-1)

' Znajdujemy największą sumę podciągu
maxSum(NN, T(), ms, ip, ik)

' Wyświetlamy wyniki:
print "ms = "; ms
print "ip = "; ip
print "ik = "; ik
print
piszT(T(), ip, ik)
end

Python (dodatek)

# Największa suma podciągu
# Algorytm prosty
# Data:   22.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

import random

N = 20  # liczba elementów ciągu


# Procedura znajduje największą
# sumę podciągu algorytmem prostym
# --------------------------------
def maxsum(n, t, mp):
    # Najmniejsza liczba integer
    mp[0] = -2147483648
    for i in range(n):
        bs = 0 # Bieżąca suma
        for j in range(i, n):
            bs += t[j]
            if bs > mp[0]:
                mp[0] = bs # Uaktualniamy
                mp[1] = i
                mp[2] = j


# Procedura wypisuje zawartość tablicy
#-------------------------------------
def pisz_t(t, mp):
    for i in range(mp[1], mp[2]+1):
        print("%4d" % i, end="")
    print()
    for i in range(mp[1], mp[2]+1):
        print("%4d" % t[i], end="")
    print()
    print()


msipik = [0, 0, N-1]
t = [random.randrange(-99, 100) for i in range(N)]
# Wyświetlamy cały ciąg
pisz_t(t, msipik)
# Znajdujemy największą sumę podciągu
maxsum(N, t, msipik)
# Wyświetlamy wyniki:
print("ms =", msipik[0])
print("ip =", msipik[1])
print("ik =", msipik[2])
print()
pisz_t(t, msipik)
print()

Wynik:

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19
  85 -41 -55  48  22   5  24  43 -39  92 -35 -54  35 -49  18 -96 -31 -43   1 -89

ms = 195
ip = 3
ik = 9

   3   4   5   6   7   8   9
  48  22   5  24  43 -39  92

do podrozdziału do strony

Algorytm z poprzedniego rozdziału ma czasową złożoność czasową klasy O(n²). Istnieje lepszy algorytm pracujący w klasie liniowej O(n). Algorytm ten został opublikowany w latach 80-tych ubiegłego wieku przez Josepha Kadane'a i otrzymał na jego cześć nazwę algorytmu Kadane'a.

Algorytm Kadane'a wykorzystuje programowanie dynamiczne (ang. dynamic programming). Polega ono na tym, iż w kolejnym kroku wykorzystywane są wyniki obliczone w kroku poprzednim.

W algorytmie będziemy pamiętać:

Największą wartość sumy częściowej w zmiennej ms.
Bieżąco wyliczaną sumę częściową w zmiennej bs.
Indeksy startu i końca podciągu o bieżąco największej sumie w zmiennych ip oraz ik.
Początek podzbioru w zmiennej s.

Zasada działania jest następująca:

Rozpoczynamy od wyzerowania wszystkich zmiennych. Następnie wykonywana jest pętla przechodząca przez kolejne elementy zbioru. Na początku każdego obiegu do zmiennej bs dodajemy bieżący element zbioru. Jeśli wynikiem jest wartość ujemna, to zmienną bs zerujemy, a do zmiennej startu podciągu s wstawiamy następną pozycję w zbiorze. W ten sposób eliminujemy podzbiory rozpoczynające się liczbą ujemną. Na koniec sprawdzamy, czy suma częściowa bs jest większa od największej sumy ms. Jeśli tak, to do ms przepisujemy bs i zapamiętujemy bieżącą pozycję podzbioru w ip i ik. Gdy pętla przejdzie wszystkie elementy zbioru, w ms będzie wartość największej sumy, a w ip oraz ik odpowiednio indeksy początku i końca podzbioru o największej sumie elementów.

Algorytm Kadane'a znajdowania największej sumy podciągu

Wejście:

n : liczba elementów tablicy, n ∈ N.
T : tablica n-elementowa z ciągiem liczb. Liczby mogą być dodatnie i ujemne, lecz wymaga się, aby przynajmniej jedna z nich była większa od zera.

Wyjście:

ms : największa suma podciągu. typ ten sam, co typ elementów tablicy.
ip : indeks pierwszego elementu podciągu, ip ∈ C.
ik : indeks ostatniego elementu podciągu, ik ∈ C.

Jeśli ms = 0, to podciąg o największej sumie elementów nie został znaleziony, a wynik jest najprawdopodobniej ujemny.

Lista kroków:

K01: ms ← najmniejsza liczba
K02: s ← bs ← ip ← ik ← 0 ; Zerujemy zmienne
K03: Dla i = 0, 1, …, n-1:   ; Kolejne elementy
     wykonuj kroki K04…K09
K04:   bs ← bs+T[i]     ; tworzymy sumę częściową
K05:   Jeśli bs < 0, to   ; likwidujemy sumy ujemne
         bs ← 0;
         s ← i+1
K06:   Jeśli bs ≤ ms, to
         następny obieg pętli K3
K07:   ms ← bs            ; zapamiętujemy sumy maksymalne
K08:   ip ← s             ; pozycja początku podciągu
K09:   ik ← i             ; pozycja końca podciągu
K10: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Poniższy program tworzy tablicę 20 elementową i wypełnia ją liczbami pseudolosowymi od -99 do 99. Następnie znajduje największą sumę podciągu oraz pozycję tego podciągu.

Pascal

// Największa suma podciągu
// Algorytm Kadane'a
// Data:   22.02.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

const
  N = 20; // liczba elementów ciągu

// Procedura znajduje największą
// sumę podciągu algorytmem prostym
//---------------------------------
procedure maxSum(n : integer;
                 var T : array of integer;
                 var ms, ip, ik : integer);
// Elementy pomocnicze
var i, bs, s : integer;

begin
    ms := -2147483648;   // Najmniejsza liczba integer
    s := 0; bs := 0; ip := 0; ik := 0;
    for i := 0 to n-1 do
    begin
        inc(bs, T[i]);   // Suma częściowa
        if bs < 0 then   // Suma ujemna?
        begin
            bs := 0;     // Zerujemy sumę ujemną
            s  := i+1; // Nowy początek podzbioru
        end;
        if bs > ms then  // Suma > max?
        begin
            ms := bs; // Uaktualniamy sumę
            ip := s;  // Początek podzbioru
            ik := i;  // Koniec podzbioru
        end;
    end;
end;

// Procedura wypisuje zawartość tablicy
//-------------------------------------
procedure piszT(var T : array of integer;
                ip, ik : integer);
var i : integer;

begin
    for i := ip to ik do write(i : 4);
    writeln;
    for i := ip to ik do write(T[i] : 4);
    writeln;
    writeln;
end;

var
  T : array [0..N-1] of integer;
  i, ip, ik, ms : integer;

begin
    randomize;
    for i := 0 to N-1 do
        T[i] := -99+random(199);

    // Wyświetlamy cały ciąg
    piszT(T, 0, N-1);

    // Znajdujemy największą sumę podciągu
    maxSum(N, T, ms, ip, ik);

    // Wyświetlamy wyniki:
    writeln('ms = ', ms);
    writeln('ip = ', ip);
    writeln('ik = ', ik);
    writeln;
    piszT(T, ip, ik);
end.

C++

// Największa suma podciągu
// Algorytm Kadane'a
// Data:   22.02.2024
// (C)2024 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

using namespace std;

const int N = 20; // liczba elementów ciągu

// Funkcja znajduje największą sumę
// podciągu algorytmem Kadane'a
//---------------------------------
void maxSum(int n, int T[], 
            int & ms, int & ip, int & ik)
{
    int i, bs, s; // Elementy pomocnicze

    ms = INT_MIN; // Najmniejsza liczba INT
    s = bs = ip = ik = 0; // Zerujemy zmienne
    for(i = 0; i < n; i++) // Kolejne elementy
    {
        bs += T[i];    // Suma częściowa
        if(bs < 0)     // Suma ujemna?
        {
            bs = 0;    // Zerujemy sumę ujemną
            s = i+1; // Nowy początek podzbioru
        }
        if(bs > ms)  // Suma większa od max?
        {
            ms = bs; // Uaktualniamy sumę
            ip = s;  // Początek podzbioru
            ik = i;  // Koniec podzbioru
        }
    }
}

// Funkcja wypisuje zawartość tablicy
//-----------------------------------
void piszT(int T[], int ip, int ik)
{
    int i;
    for(i = ip; i <= ik; i++)
        cout << setw(4) << i;
    if(ik-ip < 19) cout << endl;
    for(i = ip; i <= ik; i++)
        cout << setw(4) << T[i];
    cout << endl << endl;
}

int main()
{
    int T[N], i, ip, ik, ms;

    srand(time(NULL));
    for(i = 0; i < N; i++)
        T[i] = -99+rand() % 199;

    // Wyświetlamy cały ciąg
    piszT(T, 0, N-1);

    // Znajdujemy największą sumę podciągu
    maxSum(N, T, ms, ip, ik);

    // Wyświetlamy wyniki:
    cout << "ms = " << ms << endl
         << "ip = " << ip << endl
         << "ik = " << ik << endl << endl;
    piszT(T, ip, ik);
    return 0;
}

Basic

' Największa suma podciągu
' Algorytm Kadane'a
' Data:   22.02.2024
' (C)2024 mgr Jerzy Wałaszek
'---------------------------

const NN = 20 ' liczba elementów ciągu

' Funkcja znajduje największą
' sumę podciągu algorytmem prostym
'---------------------------------
sub maxSum(byval n as integer, _
           T() as integer, _
           byref ms as integer, _
           byref ip as integer, _
           byref ik as integer)

    ' Elementy pomocnicze
    dim as integer i, bs, s

    ms = -2147483647 ' Najmniejsza liczba INT
    s  = 0
    bs = 0
    ip = 0
    ik = 0 ' Zerujemy zmienne
    for i = 0 to n-1
        bs += T(i)
        if bs < 0 then
            bs = 0
            s = i+1
        end if
        if bs > ms then
            ms = bs ' Uaktualniamy
            ip = s
            ik = i
        end if
    next
end sub

' Funkcja wypisuje zawartość tablicy
'-----------------------------------
sub piszT(T() as integer, _
          iss as integer, _
          ik as integer)
   
    dim i as integer
    for i = iss to ik: print using "####"; i;: next
    print
    for i = iss to ik: print using "####"; T(i);: next
    print: print
end sub

dim as integer T(NN), i, ip, ik, ms

randomize
for i = 0 to NN-1
    T(i) = -99+int(rnd * 199)
next
   
' Wyświetlamy cały ciąg
piszT(T(), 0, NN-1)

' Znajdujemy największą sumę podciągu
maxSum(NN, T(), ms, ip, ik)

' Wyświetlamy wyniki:
print "ms = "; ms
print "ip = "; ip
print "ik = "; ik
print
piszT(T(), ip, ik)
end

Python (dodatek)

# Największa suma podciągu
# Algorytm Kadane'a
# Data:   22.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

import random

N = 20  # liczba elementów ciągu


# Procedura znajduje największą
# sumę podciągu algorytmem prostym
# --------------------------------
def maxsum(n, t, mp):
    # Najmniejsza liczba integer
    mp[0] = -2147483648
    s, bs = 0, 0
    for i in range(n):
        bs += t[i] # Bieżąca suma
        if bs < 0:
            bs = 0
            s = i+1
        if bs > mp[0]:
            mp[0] = bs # Uaktualniamy
            mp[1] = s
            mp[2] = i


# Procedura wypisuje zawartość tablicy
#-------------------------------------
def pisz_t(t, mp):
    for i in range(mp[1], mp[2]+1):
        print("%4d" % i, end="")
    print()
    for i in range(mp[1], mp[2]+1):
        print("%4d" % t[i], end="")
    print()
    print()


t = [random.randrange(-99, 100) for i in range(N)]
msipik = [0, 0, N-1]
# Wyświetlamy cały ciąg
pisz_t(t, msipik)
# Znajdujemy największą sumę podciągu
maxsum(N, t, msipik)
# Wyświetlamy wyniki:
print("ms =", msipik[0])
print("ip =", msipik[1])
print("ik =", msipik[2])
print()
pisz_t(t, msipik)
print()

Algorytm Kadane'a nadaje się do zbiorów posiadających przynajmniej jedną wartość dodatnią. Jeśli wszystkie elementy zbioru są ujemne, to algorytm zwróci wartość zero, jako wartość największej sumy podciągu, co jest błędne-pierwszy algorytm zwróci w tym przypadku wartość najbliższej zeru liczby ujemnej w zbiorze. Zaletą algorytmu Kadane'a jest jego niewątpliwa prostota i szybkość pracy.

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Podzbiór o największej sumie elementów

Problem

Największa suma podciągu

Rozwiązanie proste o klasie złożoności O(n²)

Algorytm znajdowania największej sumy podciągu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie ulepszone o klasie złożoności O(n)

Algorytm Kadane'a znajdowania największej sumy podciągu

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Podzbiór o największej sumie elementów

Problem

Największa suma podciągu

Rozwiązanie proste o klasie złożoności O(n2)

Algorytm znajdowania największej sumy podciągu

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie ulepszone o klasie złożoności O(n)

Algorytm Kadane'a znajdowania największej sumy podciągu

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Rozwiązanie proste o klasie złożoności O(n²)