Одсецање

Увод

Одсецање је врло једноставна и интуитивна техника за снижавање временске сложености израчунавања. Централна идеја је следећа:

Стандардне ситуације у којима можемо применити одсецање су следеће:

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

Иако примамљиво, одсецање је врло опасно ако се не врши пажљиво. Пре примене одсецања морамо да будемо апсолутно сигурни да је одсецање оправдано и да се у одбаченом делу простора претраге решења заиста не може налазити решење проблема.

У наставку ћемо се позабавити неким карактеристичним проблемима који најбоље илуструју смисао одсецања. Најпознатији пример одсецања је бинарна претрага која у свакој итерацији одбацујемо половину преосталог простора претраге. Поред тога, одсецање се често јавља као компонента сложенијих алгоритама претраге, попут бектрекинга, о чему ће бити речи касније.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.

Задатак 1

Написати програм који испитује да ли је унети природни број прост.

Улаз: Са стандардног улаза уноси се један природан број $n$ ($1 \le n \le 10^9$).

Излаз: На стандардни излаз исписати Da ако је број прост, иначе исписати Ne.

Решење

Да бисмо решили задатак можемо да кренемо од дефиниције простог броја која каже да је број прост ако је дељив само бројем 1 и самим собом. Другим речима, ако нема правих делилаца. Пратећи дефиницију, можемо врло лако да напишемо следећу функцију која проверава да ли је број прост:

static bool prost(int x)
{
    int brDelilaca = 0;
    for (int i = 1; i <= x; i++)
    {
        if (x % i == 0)
        {
            brDelilaca += 1;
        }
    }
    return brDelilaca == 2;
}

Прво одсецање које можемо да уочимо је непотребно проверавање делилаца $1$ и $х$. Довољно је да испитујемо само праве делиоце. Треба приметити да у овом приступу не испитујемо да ли је прослеђени број једнак 1. 1 није прост број, па морамо посебно да испитамо тај случај.

static bool prost_2(int x)
{
    if (x == 1) 
    {
        return false;
    }
    int brDelilaca = 0;
    for (int i = 2; i <= x - 1; i++)
    {
        if (x % i == 0)
        {
            brDelilaca += 1;
        }
    }
    return brDelilaca == 0;
}

Наредно одсецање које се лако уочава, јесте смањивање опсега бројева које треба испитати. Прецизније, највећи прави делилац било ког броја може бити $х/2$. Због тога, вредност бројача у петљи можемо ограничити тако да иде само до половине броја. Ефикаснија верзија алгоритма постаће:

static bool prost_3(int x)
{
    if (x == 1) 
    {
        return false;
    }
    int brDelilaca = 0;
    for (int i = 2; i <= x/2; i++)
    {
        if (x % i == 0)
        {
            brDelilaca += 1;
        }
    }
    return brDelilaca == 0;
}

Врло лако се закључује да број неће бити прост чим одредимо најмањи прави делилац броја. Заиста, ако нађемо бар једног делиоца, нема потребе да бројимо све праве делиоце тог броја. Дакле, потребно је да применимо рано заустављање. Чим наиђемо на правог делиоца у претрази, одмах враћамо информацију да број није прост. Ако прођемо кроз све кандидате и не нађемо делиоца, јасно је да број мора бити прост:

static bool prost_4(int x)
{
    if (x == 1) 
    {
        return false;
    }
    for (int i = 2; i <= x/2; i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}

Следеће одсецање које се лако уочава јесте да сви парни бројеви већи од 2 не могу бити прости. Због тога, можемо да раздвојимо разматрање парних и непарних бројева. Двојка је једини паран просто број, док све остале парне бројеве можемо да одбацимо као непросте, па нам у петљи остаје само да испитамо непарне делиоце.

static bool prost_5(int x)
{
    if (x == 1) 
    {
        return false;
    }
    if (x == 2)
    {
        return true;
    }
    if (x % 2 == 0)
    {
        return false;
    }
    for (int i = 3; i <= x / 2; i += 2)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}

На крају, коначно одсецање које можемо да применимо ослања се на комутативност множења. На пример, можемо да покушамо да запишемо број 16 као производ два природна броја: То можемо да урадимо на следећи начин:

$\begin{aligned}16 &= 1 \cdot 16 \\ &= 2 \cdot 8 \\ &= 4 \cdot 4 \\ &= 8 \cdot 2 \\ &= 16 \cdot 1\end{aligned}$

Можемо да искористимо комутативност и да се договоримо да први чинилац увек мора бити мањи или једнак од другог. Због тога, довољно је да испитујемо кандидате за делиоце само до броја $\sqrt{n}$, па добијамо следећи алгоритам:

static bool prost_6(int x)
{
    if (x == 1) 
    {
        return false;
    }
    if (x == 2)
    {
        return true;
    }
    if (x % 2 == 0)
    {
        return false;
    }
    for (int i = 3; i*i <= x; i += 2)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}

У овом решењу је важно нагласити врло чест трик који се користи у испитивању граница у алгоритмици. Ради се о провери услова у линији 15. Уместо да сваки пут упоређујемо вредност параметра $i$ са $\sqrt{x}$, често се користи еквивалентан услов $i*i \le x$. Разлог за то крије се у архитектури рачунара. Израчунавање математичких функција са реалним бројевима је много спорије од израчунавања основних аритметичких операција над целим бројевима. Поред тога, приликом поређења вредности увек је боље остати у оквирима истог типа података, јер се тиме не ограничавамо значајним и сигурним цифрама и грешкама заокругљивања.

Временска сложеност првог наивног алгоритма је $O(n)$, док је временска сложеност последњег ефикасног алгоритма $O(\sqrt{n})$. Иако ова временска уштеда не делује баш импресивно, треба узети у обзир да се ради о асимптотској сложености која до изаражаја долази тек када се ради о улазним параметрима великих димензија. Ако као улазни параметар алгоритму проследимо прост број $\approx 10^6$, тада ће наивном алгоритму бити потребно приближно милион дељења да утврди да се ради о простом броју. Са друге стране, ефикасни алгоритам ће доћи до истог закључка са приближно хиљаду дељења. Просторна сложеност оба алгоритма је константна. Одређивање временских и просторних сложености осталих приказаних решења остављамо читаоцу за вежбу.

У пракси, испитивање да ли је број прост се на овај начин може урадити за вредности $n \le 10^9$, док се за веће вредности користе други алгоритми. Најпознатији су Фермаов тест и Рабин-Милеров тест којим се испитује колико је вероватно да је дати број прост. Заинтересовани читаоци могу потражити детаље у ЦЛРС.

Задатак 2

Написати програм који одређује колико има простих бројева мањих или једнаких природном броју $n$.

Улаз: Са стандардног улаза уноси се један природан број $n$. ($1 \le n \le 10^6$).

Излаз: На стандардни излаз исписати колико има простих бројева мањих или једнаких $n$.

Решење

Као и у претходном задатку, крећемо од наивног приступа. Дакле, потребно је да прођемо кроз све природне бројеве $\le n$ и да за сваки тај број проверимо да ли је прост. Ако је прост, увећаћемо бројач. На крају, вредност бројача ће бити број простих бројева $\le n$. Решење је у наставку:

static int brojProstih_naivno(int n) 
{
    int brojProstih = 0;
    for (int i = 1; i <= n; i++) {
        if (prost(i))
            brojProstih++;
    }
    return brojProstih;
}

У приказаном решењу претпостављамо да функција prost(int х) имплементира ефикасну верзију алгоритма за испитивање да ли је број прост из претходног задатка. Имајући то у виду, укупна временска сложеност приказаног решења ће бити $O(n \sqrt{n})$. Објашњење овог закључка је врло једноставно, да бисмо испитали да ли је било који број прост треба нам $O(\sqrt{n})$ времена. С обзиром да испитујемо $n$ бројева, укупна сложеност ће бити управо $O(n \sqrt{n})$. Просторна сложеност приказаног решења је константна.

Приказана идеја није лоша, али није практична за велике вредности улазног параметра $n$. Разлог зашто наш алгоритам није довољно добар се може врло лако уочити. Са сваким следећим бројем који разматрама, поновићемо испитивање са великим бројем истих кандидата. Прецизније, велики број пута ћемо испитивати исте делиоце. Да бисмо учинили наш алгоритам ефикаснији, требало би да сваког кандидата делиоца разматрамо тачно једног за сваки број.

На старту, претпоставићемо да су сви бројеви из скупа $\{1, 2, \ldots, n \}$ прости. Игнорисаћемо број $1$, јер за њега знамо да није ни прост ни непрост. Дакле, крећемо од броја $2$ као најмањег простог броја и редом елиминишемо из датог скупа природних бројева све његове умношке. Затим, прећићемо на број $3$ и елиминисаћемо све његове умношке. Треба приметити да смо број $6 = 2 \cdot 3$ већ елиминисали, па као први број одакле крећемо са елиминисањем умножака можемо да узмемо број $9 = 3^2$. После броја $3$, поступак треба да наставимо од првог неелиминисанот броја, што ће бити број $5$. Поступак настављамо све док постоје неелиминисани кандидати делиоци који су $\le \sqrt{n}$. На овај начин ћемо “просејати” све просте бројеве из скупа природних бројева $\{1, 2, \ldots, n \}$. Описани поступак се назива Ератостеново сито и један је од првих документованих алгоритама. Имплементација је у наставку:

static bool[] eratostenovo_sito(int n)
{
    bool[] prosti = new int[n + 1];
    for (int i = 0; i <= n; i++)
    {
        prosti[i] = true;
    }
    for (int i = 2; i * i <= n; i++)
    {
        if (prosti[i] == true)
        {
            for (int j = i * i; j <= n; j += i)
            {
                prosti[j] = false;
            }
        }
    }
    return prosti;
}

У имплементацији Ератостеновог сита постоји неколико осетљивих места:

• Дефинисање низа индикатора - Треба пажљиво погледати линије 3-7. Величина низа мора бити $n+1$, јер нам треба информација о томе да ли је и сам број $n$ прост или не, тј. мораћемо да прочитамо вредност prosti[n] у низу.
• Услов у спољашњој петљи - Обратите пажњу на линију 8 и проверу услова $i*i \le n$. Ради се управо о трику којим испитујемо да ли је параметар $i$ мањи или једнак од вредности $\sqrt{n}$. Погрешно постављање границе у услову петље ће значајно повећати временску сложеност алгоритма.
• Почетна вредност и корак у унутрашњој петљи - Обратите пажњу на линију 12. Почетна вредност за параметар $ј$ је $i*i$, а корак којим увећавамо параметар $ј$ је $i$. Погрешно иницијализовање и увећавање параметра $ј$ ће значајно повећати временску сложеност алгоритма.
• Просторна сложеност - Приметимо да у имплементацији Ератостеновог сита користимо помоћни низ индикатора да бисмо чували информације о простости бројева. Величина тог низа директно зависи од величине улаза, па наш алгоритам има просторну сложеност $O(n)$.

Ератостеново сито је временски изузетно ефикасан алгоритам и његова временска сложеност је $О(n \cdot \log \log n)$. Иако временски ефикасан, ограничавајући фактор Ератостеновог сита је његова просторна сложеност. У пракси, Ератостеново сито има смисла користити за вредности $n \le 10^6$.

На крају, остаје нам само да решимо задатак тако што ћемо пребројати колико бројева је у низу индикатора остало просто након Ератостеновог сита.

static int broj_prostih(int n)
{
    bool[] prosti = eratostenovo_sito(n);
    int br = 0;
    for (int i = 2; i <= n; i++)
    {
        if (prosti[i])
        {
            br++;
        }
    }
    return br;
}

Задатак 3

Написати програм који за дати природни број $n$ одређује колико има парова простих бројева $(p,q)$ таквих да је $p < q$ и $p + q \le n$ је такође прост.

Улаз: Са стандардног улаза уноси се један природан број $n$. ($1 \le n \le 10^6$).

Излаз: На стандардни излаз исписати тражени број парова простих бројева чији је збир прост.

Решење

Као и увек до сада, крећемо од наивног решења које директно следи из текста задатка. Потребно је да проверимо све могуће дозвољене вредности за параметре $p$ и $q$ и да за њих испитамо да ли важи услов задатка. Решење је у наставку:

static int broj_prostih_zbirova(int n)
{
    int br = 0;
    for (int p = 2; p <= n; p++) {
        for (int q = p + 1; q <= n; q++) {
            if (prost(p) && prost(q) && (p + q <= n) && prost(p + q))
            {
                br++;
            }
        }
    }
    return br;
}

Очигледно је да ово решење није ефикасно. Временска сложеност овог алгоритма је $O(n^2 \cdot \sqrt{n})$. Проблем у овом решењу је што потпуно некритички испитујемо простост сваког броја испочетка. Убрзање бисмо могли да добијемо када бисмо унапред издвојили све просте бројеве и онда само њих испитивали, тј. можемо да искористимо Ератостеново сито.

static int broj_prostih_zbirova(int n)
{
    int br = 0;
    bool[] prosti = eratostenovo_sito(n);
    for (int p = 2; p <= n; p++) {
        for (int q = p + 1; q <= n; q++) {
            if (prosti[p] && prosti[q] && (p + q <= n) && prost[p + q])
            {
                br++;
            }
        }
    }
    return br;
}

Одређивање временске сложености приказаног решења остављамо читаоцу за вежбу.

Приказано решење можемо даље убрзати искоришћавањем услова задатка. Бројеви $p$ и $q$ морају бити прости, али мора бити прост и њихов збир $p + q$. Јасно је да њихов збир мора бити непаран број, а то можемо добити само ако саберемо паран и непаран број. Због услова $p < q$, јасно је да $p$ мора бити једнако $2$. Дакле, остаје нам само да испитамо вредности $q$. Због тога, решење постаје:

static int broj_prostih_zbirova(int n)
{
    int br = 0;
    bool[] prosti = eratostenovo_sito(n);
    int p = 2;
    for (int q = p + 1; p + q <= n; q += 2)
    {
        if (prost[q] && prost[p + q])
            br++;
    }
    return br;
}

Линије $6-10$ представљају фрагмент кода линеарне сложености, па временском сложеношћу алгоритма доминира извршавање функције eratostenovo_sito(). Укупна временска и просторна сложеност решења биће једнаки временској и просторној сложености Ератостеновог сита.

Задатак 4

Корисник уноси природни број $n \le 10^6$. Написати програм који одређује факторизацију броја.

Улаз: Са стандардног улаза уноси се један природан број $n$. ($1 \le n \le 10^6$).

Излаз: На стандардни излаз исписати низ бројева који представља факторизацију броја $n$.

Решење

Наивно, могли бисмо да покушамо да имплементирамо поступак којим би факторизацију датог броја одредило дете у петом разреду. Редом бисмо испитивали све просте бројеве почевши од најмањег и делили бисмо полазни број датим простим делиоцем све док можемо. Поступак бисмо зауставили када бисмо полазни број свели до јединице. Јасно је да је временска сложеност овог поступка изузетно висока и нећемо се детаљније бавити овом идејом.

Ефикасније решење је засновано на идеји Ератостеновог сита, Уместо да чувамо низ индикатора који нам говоре да ли је изабрани број прост или не, модификоваћемо тај низ тако да за сваки број чувамо његов најмањи прост делилац. Као што смо на почетку алгоритма Ератостеново сито претпоставили да су сви бројеви прости, тако ћемо и овде претпоставити да је сваки број сам себи најмањи делилац. Током извршавања алгоритма, уписиваћемо нови мањи делилац само ако дати број није већ ажуриран у неком претходном кораку. Алгоритам којим одређујемо делиоце дат је у наставку:

static int[] odredi_najmanje_delioce(int n)
{
    int[] delioci = new int[n+1];
    for (int i = 0; i <= n; i++)
    {
        delioci[i] = i;
    }
    for (int i = 2; i * i <= n; i++)
    {
        if (delioci[i] == true)
        {
            for (int j = i * i; j <= n; j += i)
            {
                if (delioci[j] == j) 
                {
                    delioci[j] = i;
                }
            }
        }
    }
    return delioci;
}

Поред уобичајених осетљивих места у имплементацији Ератостеновог сита, овде треба посебно одратити пажњу на линије $14-17$. Провера у линији $14$ је кључна, јер омогућава памћење најмањег простог делиоца.

Након генерисања делилаца, остаје нам само да реконструишемо факторизацију стандардним ходом уназад. Решење је у наставку:

static int[] faktorizacija(int n)
{
    int[] delioci = odredi_najmanje_delioce(n);
    List<int> rezultat = new List<int>();
    while (n > 1)
    {
        int faktor = delioci[n];
        rezultat.Add(faktor);
        n = n / faktor;
    }
    return rezultat.ToArray();
}

Временска сложеност алгоритма је једнака сложености Ератостеновог сита. Петља којом попуњавамо листу фактора има логаритамску сложеност, што је мање од временске сложености Ератостеновог сита. Просторна сложеност алгоритма је такође једнака сложености Ератостеновог сита.

Задатак 5

Кошаркашки тим је играо пуно утакмица у сезони. У свакој утакмици остварио је или победу или пораз. Напиши програм који одређује дужину најдуже серије победа у узастопним мечевима током сезоне.

Улаз: Са стандардног улаза се учитава број $n$ ($5 \le n \le 60$). У наредних $n$ редова учитаваjу се бројеви 1 (победа), 0 (нерешено), -1 (пораз).

Излаз: На стандардни излаз исписати један природан број који представља тражену дужину најдуже серије узастопних победа.

Решење

Знамо да дужина најдужег узастопног низа победа може бити у интервалу $[0,n]$. Задатак можемо да решимо директно, тако што ћемо за свако $k \in {1,2, \ldots, n}$ да испитамо да ли постоји низ победа чија је дужина барем $k$. Решење нашег задатка биће највеће $k$ за које смо пронашли одговарајућу серију.

Решење задатка можемо да поделимо у две мање целине:

• Испитивање да ли постоји серија дужине $k$.
• Претраге серија по сваком $k \in {1,2, \ldots, n}$.

Испитивање да ли постоји серија дужине $k$ је прилично лак задатак. Потребно је да фиксирамо почетну позицију серије у низу резултата и да проверимо да ли следећих $k$ елемената низа има вредност $1$. Да бисмо проверили цео низ, потребно је да поновимо исти поступак од сваке могуће почетне позиције.

static bool serija_pobeda_duzine_k(int[] niz, int k)
{
    for (int i = 0; i <= niz.Length - k; i++)
    {
        int j = 0;
        while (j < k && niz[i + ј] == 1)
        {
            j++;
        }
        if (j == k)
            return true;
    }
    return false;
}

У приказаном решењу спољашња петља фиксира почетну позицију $i$, док унутрашња петља броји узастопне јединице почевши од позиције $i$. У случају да избројимо тачно $k$ узастопних јединица, прекидамо претрагу и враћамо true. Aко испитамо све могуће почетне позиције, тј. извршимо петљу до краја јасно је да не постоји серија дужине $k$. Временска сложеност овог поступка је $O(k \cdot (n-k)) \approx O(n^2)$.

Сада, када знамо да испитамо да ли постоји серија победа дужине $k$ можемо да одредимо најдужу серију победа једноставним испитивањем сваког могућег $k$. Комплетно наивно решење задатка је у наставку:

static int najduza_serija_pobeda(int[] niz)
{
    int maksK = 0;
    for (int k = 1; k <= niz.Length; k++)
    {
        if (serija_pobeda_duzine_k(niz, k))
        {
            maksK = k;
        }
    }
    return maksK;
}

Временска сложеност наивног решења је $О(n^3)$. Детаље одређивања остављамо читаоцу за вежбу.

Задатак се може решити у значајној нижој временској сложености. Потребно је приметити два једноставна одсецања:

• Приликом испитивања да ли постоји серија победа дужине $k$ често не постоји потреба да испитујемо сваку могућу позицију. На пример, ако је $k=4$ и ми утврдимо да од позиције $i$ редом иду 3 узастопне победе, па пораз, можемо одмах да направимо прескок и да следећу претрагу покренемо од позиције $i+4$, јер је јасно да се на свим претходним позицијама не може наћи серија дужа од $3$.
• Једном када смо испитали вредност елемента на позицији $i$ у низу, не постоји потреба да га икада поново испитујемо. Овај закључак је природан, јер елемент на позицији $i$ нема никакав утицај на наредне елементе. Прецизније, потребно је да уместо проверавања сваког могућег $k$ током проласка кроз низ рачунамо текућу дужину серије победа. Са сваком “непобедом” на коју наиђемо у низу потребно је да упоредимо текућу серију са максималном серијом и да је по потреби ажурирамо.

Прво описано одсецање води ка асимптотски бољем решењу, али и даље исте сложености. Друго одсецање води ка решењу које је значајно ефикасније и које је приказано у наставку:

static int najduza_serija_pobeda(int[] niz)
{
    int najduzaSerija = 0;
    int tekucaSerija = 0;
    for (int i = 0; i < niz.Length; i++)
    {
        if (niz[i] == 1)
        {
            tekucaSerija += 1;
            if (tekucaSerija > najduzaSerija)
            {
                najduzaSerija = tekucaSerija;
            }
        }
        else
        {
            tekucaSerija = 0;
        }
    }
    return najduzaSerija;
}

Временска сложеност приказаног решења је $О(n)$, јер сваки елемент низа разматрамо тачно једном.

Задатак 6

Дат је низ $a$ целих бројева, дужине $n$. Написати програм којим се одређује на колико начина можемо изабрати растуће сегменте у низу. Растући сегмент чине узастопни елементи низа $a_p < a_{p+1} < \ldots < a_q , 0 \le p < q < n$.

Улаз: Прва линија стандардног улаза садржи природан број $n$ ($2 \le n\le 10000$), број елемената низа. У свакој од $n$ наредних линија стандардног улаза, налази по један члан низа.

Излаз: На стандардном излазу приказати у једној линији број растућих сегмената датог низа.

Решење

Пре него што кренемо са описом решења задатка, битно је нагласити услове из поставке. Услов $0 \le p < q < n$ нам говори да дужина сегмента може изности најмање $2$.

Наивно решење се може конструисати директно из текста задатка. Потребно је само да пребројимо све могуће растуће сегменте чије дужине редом могу бити $k \in {2,3, \ldots, n}$. Слично као у претходном задатку, решење можемо да разложимо на две мање целине:

• Испитивање да ли је сегмент дужине $k$ који почиње на позицији $p$ растући.
• Испитивање свих сегмената за све могуће вредности параметара $p$ и $k$.

Да бисмо утврдили да ли је неки сегмент растући потребно је да испитујемо његове елементе по паровима, тј. треба да анализирамо суседне елемент. Анализа суседних је честа техника која се користи у конструкцији алгоритама. Решење је приказано у наставку:

static bool rastuci(int[] niz, int p, int k)
{
    for (int i = 1; i < k; i++)
    {
        if (niz[p + i - 1] >= niz[p + i])
            return false;
    }
    return true;
}

Логика иза анализе суседних је врло једноставна у овом примеру. Ако је претходни елемент, тј. сусед, већи или једнак од текућег елемента, онда низ сигурно није растући. Ако испитамо читав сегмент и не наиђемо на такав случај, онда је сегмент растући. Временска сложеност описаног поступка је линеарна, тј. $О(n)$.

Сада, када знамо како да испитамо да ли је сегмент растући, остаје нам само да пребројимо све сегменте који задовољавају дати услов. Дакле, за сваку дужину сегмента треба да испитамо све могуће почетне позиције. Решење је у прилогу:

static int broj_rastucih(int[] niz)
{
    int br = 0;
    for (int k = 2; k <= niz.Length; k++)
    {
        for (int p = 0; p <= niz.Length - k; p++)
        {
            if (rastuci(niz, p, k))
            {
                br += 1;
            }
        }
    }
    return br;
}

Јасно је да ово решење није ефикасно и да би требало да га побољшамо. Да бисмо то урадили, морамо пажљиво да анализирамо шта се дешава са нашим сегментима. Размотримо пример низа

$$1 \quad 2 \quad 3 \quad 4 \quad 5 \quad -3 \quad -2 \quad -1$$

Из текста задатка је јасно да је први растући сегмент који задовољава наш услов низ

$$1 \quad 2.$$

Ради лакшег бројања сегмената, можемо да их вежемо за позицију на којој се завршавају. Дакле, број растућих сегмената на позицијама $0$ и $1$ биће редом $S_0 = 0$ и $S_1 = 1$. Треба да размотримо како се мења број растућих сегмената када додамо следећи елемент, тј. колико ћемо имати растућих сегмената који се завршавају на позицији $2$. Дакле, додајемо елемент $3$ и добијамо следеће подскупове.

$$\begin{aligned} &1 \quad 2 \\ &1 \quad 2 \quad 3 \\ &2 \quad 3 \end{aligned}$$

Одавде закључујемо да се на позији $2$ у низу завршавају два растућа сегмента, тј. $S_2 = 2$. Наставимо даље наше разматрање додавањем броја $4$ у скуп.

$$\begin{aligned} &1 \quad 2 \\ &1 \quad 2 \quad 3 \\ &2 \quad 3 \\ &1 \quad 2 \quad 3 \quad 4 \\ &2 \quad 3 \quad 4 \\ &3 \quad 4 \end{aligned}$$

Одавде закључујемо да се на позији $3$ у низу завршавају два растућа сегмента, тј. $S_3 = 3$. Лако можемо да закључимо да ће укупан број растућих сегмената на позицији $3$ бити управо збир броја сегмената који се завршавају на свим ранијим позицијама. тј. $S = S_0 + S_1 + S_2 + S_3$. Поступак можемо да наставимо, али већ одавде се може лако закључити да постоји веза између дужине растућег подниза и број подскупова коју можемо описати следећим правилом:

Нека је досадашњи растући сегмент био дужине $k$. Када га проширимо са наредним елементом, тада ће се укупан број подскупова увећати за $k+1$, тј. за текућу дужину растућег сегмента.

Да би овај закључак имао смисла, дужине сегмената морамо да бројимо од 0.

Формално, закључак бисмо морали да покажемо индукцијом, али то остављамо читаоцу за вежбу. Из описа постпука, јасно је да морамо да користимо анализу суседних и да можемо да одредимо тражено решење у једном пролазу кроз низ.

static int broj_rastucih_segmenata(int[] niz)
{
    int br = 0;
    int duzinaSegmenta = 0;
    for (int i = 1; i < niz.Length; i++)
    {
        if (niz[i] > niz[i-1])
        {
            duzinaSegmenta += 1;
        }
        else
        {
            duzinaSegmenta = 0;
        }
        br += duzinaSegmenta;
    }
    return br;
}

Временска сложеност приказаног решења је линеарна, тј. $O(n)$.