Matura: C++ - podciąg o największej sumie

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
T	–	tablica n-elementowa z ciągiem liczb

Wyjście:
ms	–	największa suma podciągu
ip	–	indeks pierwszego elementu podciągu
ik	–	indeks ostatniego elementu podciągu

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

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

// Największa suma podciągu
// Algorytm prosty
//-------------------------
#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 1
//----------------------------
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 is, int ik)
{
    for(int i = is; i <= ik; i++)
        cout << setw(4) << i;
    if(ik - ip < 20) cout << endl;
    for(int i = is; 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() % 201;

    // 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;
}

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19
   0  64   5 -22  12 -59 -60  27 100  27  96 -55  97  44 -57 -36 100 -79 -53 -65

ms = 343
ip = 7
ik = 16

   7   8   9  10  11  12  13  14  15  16
  27 100  27  96 -55  97  44 -57 -36 100

Do zapamiętania:

Pojęcie podciągu.
Zasada działania algorytmu znajdowania największej sumy podciągu.
Klasa złożoności czasowej algorytmu 1.

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 dotychczas.

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
T	–	tablica n-elementowa z ciągiem liczb

Wyjście:
ms	–	największa suma podciągu
ip	–	indeks pierwszego elementu podciągu
ik	–	indeks ostatniego elementu podciągu

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

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

// Największa suma podciągu
// Algorytm Kadane'a
//-------------------------

#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,j,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
            ip = s;  // Początek podzbioru
            ik = i;  // Koniec podzbioru
        }
    }
}

// Funkcja wypisuje zawartość tablicy
//-----------------------------------
void piszT(int T[], int ip, int ik)
{
    for(int i = ip; i <= ik; i++)
        cout << setw(4) << i;
        
    if(ik - ip + 1 < 20) cout << endl;
    
    for(int 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() % 201;

    // 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;
}

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 zapamiętania:

Zasada działania algorytmu Kadane'a.
Ograniczenia algorytmu Kadane'a.
Klasa złożoności czasowej algorytmu Kadane'a.

do podrozdziału do strony

Matura - programowanie w C++

Największa suma podciągu

Największa suma podciągu

Algorytm 1

Algorytm znajdowania największej sumy podciągu

Do zapamiętania:

Algorytm 2

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

Do zapamiętania:

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