Matura - programowanie w C++

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

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