Проблем максималног подниза

У информатици, проблем максималног подниза је задатак проналажења непрекидног подниза, унутар једнодимензионалног низа бројева (мора да садржи бар један позитиван број) који има највећу суму. На пример, за низ бројева −2, 1, −3, 4, −1, 2, 1, −5, 4, непрекидни подниз са највећом сумом је 4, −1, 2, 1, чија сума износи 6.

Проблем је први поставио Улф Гренандер на Браун универзитету 1977. године, као упрошћени модел за максималну вероватноћу процене шаблона у дигитализованим сликама. Алгоритам линеарне сложености пронађен је убрзо од стране Џеј Кадана на Карнеги Мелон Универзитету.

Каданов алгоритам

Каданов алгоритам се састоји од претраживања вредности низа, израчунавајући на свакој позицији максимум подниза закључно са том позицијом у низу. Ова сума је или празна (у чијем случају је вредност суме 0) или садржи један елемент више у односу на крај максималног подниза претходне позиције. Овај проблем може бити решен следећим кодом представљеним у Пајтону.

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

Варијанта проблема која не дозвољава нулте дужине подниза као повратне вредности у случају да се цео низ састоји од негативних бројева, може се решити следећим делом кода представљеним у програмском језику 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 ;
}

Алгоритам се такође може лако модификовати тако да прати почетне и крајње индексе максималног подниза.

Због начина на који овај алгоритам користи оптималну подструктуру (крај максималног подниза на свакој позицији је израчунат на једноставан начин уз помоћ повезаног али мањег потпроблема) овај алгоритам се може представити као једноставан пример динамичког програмирања.

Сложеност Кадановог алгоритма је ${\mathcal {O}}(n)$.

Подели па владај

Подели па владај представља алгоритам у којем се већи проблем рашчлањује на више мањих, који су једноставнији за сагледавање и појединачно решавање. Ови потпроблеми се могу решавати паралелно (истовремено решавање два или више потпроблема) или један за другим.

Његова сложеност је ${\mathcal {O}}(n\log n)$.

Генерализација

Слични проблеми могу се поставити и на вишедимензионалним низовима али је њихово решење компликованије. На пример, Такаока (2002. године), Бродал и Јоргенсен (2007. године) показали су како да пронађемо највећу суму k поднизова једнодимензионалног низа оптималне временске сложености ${\mathcal {O}}(n+k)$.

Литература

• 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, стр. 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, Архивирано из оригинала (PDF) 29. 10. 2013. г., Приступљено 31. 05. 2013 .

Спољашње везе

• Kadane's Algorithm Архивирано на сајту Wayback Machine (7. септембар 2009)
• www.algorithmist.com
• alexeigor.wikidot.com
• Algorithm Design Techniques