Problem maksimalnog podniza

U informatici, problem maksimalnog podniza je zadatak pronalaženja neprekidnog podniza, unutar jednodimenzionalnog niza brojeva (mora da sadrži bar jedan pozitivan broj) koji ima najveću sumu. Na primer, za niz brojeva −2, 1, −3, 4, −1, 2, 1, −5, 4, neprekidni podniz sa najvećom sumom je 4, −1, 2, 1, čija suma iznosi 6.

Problem je prvi postavio Ulf Grenander na Braun univerzitetu 1977. godine, kao uprošćeni model za maksimalnu verovatnoću procene šablona u digitalizovanim slikama. Algoritam linearne složenosti pronađen je ubrzo od strane Džej Kadana na Karnegi Melon Univerzitetu.

Kadanov algoritam

Kadanov algoritam se sastoji od pretraživanja vrednosti niza, izračunavajući na svakoj poziciji maksimum podniza zaključno sa tom pozicijom u nizu. Ova suma je ili prazna (u čijem slučaju je vrednost sume 0) ili sadrži jedan element više u odnosu na kraj maksimalnog podniza prethodne pozicije. Ovaj problem može biti rešen sledećim kodom predstavljenim u Pajtonu.

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Varijanta problema koja ne dozvoljava nulte dužine podniza kao povratne vrednosti u slučaju da se ceo niz sastoji od negativnih brojeva, može se rešiti sledećim delom koda predstavljenim u programskom jeziku C++.

int sequence(std::vector<int>& numbers)
{
        // Initialize variables here
        int max_so_far  = numbers[0], max_ending_here = numbers[0];

        // OPTIONAL: These variables can be added in to track the position of the subarray
        // size_t begin = 0;
        // size_t begin_temp = 0;
        // size_t end = 0;

        // Find sequence by looping through
        for(size_t i = 1; i < numbers.size(); i++)
        {
                // calculate max_ending_here
                if(max_ending_here < 0)
                {
                        max_ending_here = numbers[i];
                        
                        // begin_temp = i;
                }
                else
                {
                        max_ending_here += numbers[i];
                }

                // calculate max_so_far
                if(max_ending_here >= max_so_far )
                {
                        max_so_far  = max_ending_here;
                        
                        // begin = begin_temp;
                        // end = i;
                }
        }
        return max_so_far ;
}

Algoritam se takođe može lako modifikovati tako da prati početne i krajnje indekse maksimalnog podniza.

Zbog načina na koji ovaj algoritam koristi optimalnu podstrukturu (kraj maksimalnog podniza na svakoj poziciji je izračunat na jednostavan način uz pomoć povezanog ali manjeg potproblema) ovaj algoritam se može predstaviti kao jednostavan primer dinamičkog programiranja.

Složenost Kadanovog algoritma je ${\mathcal {O}}(n)$.

Podeli pa vladaj

Podeli pa vladaj predstavlja algoritam u kojem se veći problem raščlanjuje na više manjih, koji su jednostavniji za sagledavanje i pojedinačno rešavanje. Ovi potproblemi se mogu rešavati paralelno (istovremeno rešavanje dva ili više potproblema) ili jedan za drugim.

Njegova složenost je ${\mathcal {O}}(n\log n)$.

Generalizacija

Slični problemi mogu se postaviti i na višedimenzionalnim nizovima ali je njihovo rešenje komplikovanije. Na primer, Takaoka (2002. godine), Brodal i Jorgensen (2007. godine) pokazali su kako da pronađemo najveću sumu k podnizova jednodimenzionalnog niza optimalne vremenske složenosti ${\mathcal {O}}(n+k)$.

Literatura

• Bentley, Jon (1984), „Programming pearls: algorithm design techniques”, Communications of the ACM, 27 (9): 865—873, doi:10.1145/358234.381162 .
• Brodal, Gerth Stølting; Jørgensen, Allan Grønlund (2007), „A linear time algorithm for the k maximal sums problem”, Mathematical Foundations of Computer Science 2007, Lecture Notes in Computer Science, 4708, Springer-Verlag, str. 442—453, doi:10.1007/978-3-540-74456-6_40 .
• Takaoka, T. (2002), „Efficient algorithms for the maximum subarray problem by distance matrix multiplication” (PDF), Electronic Notes in Theoretical Computer Science, 61, Arhivirano iz originala (PDF) 29. 10. 2013. g., Pristupljeno 31. 05. 2013 .

Spoljašnje veze

• Kadane's Algorithm Arhivirano na sajtu Wayback Machine (7. septembar 2009)
• www.algorithmist.com
• alexeigor.wikidot.com
• Algorithm Design Techniques