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

Из Википедије, слободне енциклопедије

У информатици, проблем максималног подниза је задатак проналажења непрекидног подниза, унутар једнодимензионалног низа бројева (мора да садржи бар један позитиван број) који има највећу суму. На пример, за низ бројева −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).

Литература[уреди]

Спољашње везе[уреди]