Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Podzbiór o największej sumie elementów

SPIS TREŚCI
Podrozdziały
Tematy pomocnicze

Problem

W n-elementowym zbiorze Z należy znaleźć podzbiór kolejnych elementów o największej sumie tych elementów.

Największa suma podciągu

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.


Na początek:  podrozdziału   strony 

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

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ć:

  1. Największą wartość sumy częściowej w zmiennej ms.
  2. Bieżąco wyliczaną sumę częściową w zmiennej bs.
  3. 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.

Zmienne pomocnicze:

i, j : przebiegają przez kolejne indeksy elementów T. ij ∈ 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:     bsbs + T[j]     ; liczymy sumę częściową
K06:     Jeśli bs  ms,
         to następny obieg K04
K07:     msbs            ; uaktualniamy zmienne wynikowe
K08:     ipi             ; indeks początku podciągu
K09:     ikj             ; 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);
// Zmienne 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)
{
    // Zmienne 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)

' Zmienne 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):
    mp[0] = -2147483648; # Najmniejsza liczba integer
    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 piszT(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 = []
msipik = [0, 0, N - 1]
for i in range(N):
    T.append(-99 + random.randrange(199))

# Wyświetlamy cały ciąg
piszT(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()
piszT(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

Na początek:  podrozdziału   strony 

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

Algorytm z poprzedniego rozdziału ma czasową złożoność czasową klasy O(n2). 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ć:

  1. Największą wartość sumy częściowej w zmiennej ms.
  2. Bieżąco wyliczaną sumę częściową w zmiennej bs.
  3. Indeksy startu i końca podciągu o bieżąco największej sumie w zmiennych ip oraz ik.
  4. 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 ipik. 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: sbsipik ← 0 ; Zerujemy zmienne
K03: Dla i = 0,1,…,n-1:   ; Kolejne elementy
     wykonuj kroki K04…K09
K04:   bsbs + T[i]     ; tworzymy sumę częściową
K05:   Jeśli bs < 0, to   ; likwidujemy sumy ujemne
         bs ← 0;
         si + 1
K06:   Jeśli bsms, to
         następny obieg pętli K3
K07:   msbs            ; zapamiętujemy sumy maksymalne
K08:   ips             ; pozycja początku podciągu
K09:   iki             ; 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);
// Zmienne 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; // Zmienne 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)

    ' Zmienne 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):
    mp[0] = -2147483648; # Najmniejsza liczba integer
    s = bs = ip = ik = 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 piszT(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 = []
msipik = [0, 0, N - 1]
for i in range(N):
    T.append(-99 + random.randrange(199))

# Wyświetlamy cały ciąg
piszT(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()
piszT(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.


Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.