Проблем максималног подниза је исти као и проблем максималног пресека. Овај водич говори о проблему кодирања у Ц++. Питање је: колики је максимални збир било ког могућег низа узастопних бројева унутар низа? Ово може значити цео низ. Овај проблем и његово решење на било ком језику називају се проблемом максималног подниза. Низ може имати могуће негативне бројеве.
Решење мора бити ефикасно. Мора да има најбржу временску сложеност. До сада, најбржи алгоритам за решење је познат у научној заједници као Каданеов алгоритам. Овај чланак објашњава Каданеов алгоритам са Ц++.
Примери података
Размотрите следећи вектор (низ):
вектор < инт > А = { 5 , - 7 , 3 , 5 , - два , 4 , - 1 } ;
Исечак (подниз) са максималним збиром је низ, {3, 5, -2, 4}, који даје збир од 10. Ниједан други могући низ, чак ни цео низ, неће дати збир до вредност 10. Цео низ даје збир од 7, што није максимални збир.
Размотрите следећи вектор:
вектор < инт > Б = { - два , 1 , - 3 , 4 , - 1 , два , 1 , - 5 , 4 } ;
Исечак (подниз) са максималним збиром је низ, {4, −1, 2, 1} који даје збир од 6. Имајте на уму да могу бити негативни бројеви унутар подниза за максималан збир.
Размотрите следећи вектор:
вектор < инт > Ц = { 3 , два , - 6 , 4 , 0 } ;
Исечак (подниз) са максималним збиром је секвенца, {3, 2} која даје збир од 5.
Размотрите следећи вектор:
вектор < инт > Д = { 3 , два , 6 , - 1 , 4 , 5 , - 1 , два } ;
Подниз са максималним сумом је низ, {3, 2, 6, -1, 4, 5, -1, 2} који даје збир од 20. То је цео низ.
Размотрите следећи вектор:
вектор < инт > Е = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , петнаест , 4 , - 8 , - петнаест , - 22 } ;
Овде постоје два подниза са максималним сумама. Већи збир је онај који се сматра решењем (одговором) за проблем максималног подниза. Поднизови су: {5, 7} са збиром 12, и {6, 5, 10, -5, 15, 4} са збиром од 35. Наравно, исечак са збиром од 35, је одговор.
Размотрите следећи вектор:
вектор < инт > Ф = { - 4 , 10 , петнаест , 9 , - 5 , - двадесет , - 3 , - 12 , - 3 , 4 , 6 , 3 , два , 8 , 3 , - 5 , - два } ;
Постоје два подниза са максималним сумама. Већи збир је онај који се сматра решењем за проблем максималног подниза. Поднизови су: {10, 15, 9} са збиром 34 и {4, 6, 3, 2, 8, 3} са збиром од 26. Наравно, исечак са збиром 34 је одговор јер је проблем тражити подниз са највећим сумом, а не подниз са већом сумом.
Развијање Каданеовог алгоритма
Информације у овом одељку туторијала нису оригинално дело Каданеа. То је ауторов сопствени начин да научи Каданеов алгоритам. Један од горњих вектора, са својим текућим укупним вредностима, налази се у овој табели:
| Подаци | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | петнаест | 4 | -8 | -петнаест | -22 |
| Руннинг Тотал | 5 | 12 | 8 | -два | -8 | -два | 3 | 13 | 8 | 23 | 27 | двадесет један | 16 | -6 |
| индекс | 0 | 1 | два | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Једанаест | 12 | 13 |
Покренути Тотал за индекс је збир свих претходних вредности укључујући и ону за индекс. Овде постоје две секвенце са максималним сумама. Они су {5, 7}, што даје збир од 12, и {6, 5, 10, -5, 15, 4}, што даје збир од 35. Редослед који даје збир од 35 је оно што се жели .
Приметите да за текуће укупне вредности постоје два врха који су вредности, 12 и 27. Ови врхови одговарају последњим индексима две секвенце.
Дакле, идеја Каданеовог алгоритма је да ради текући зброј док пореди максималне суме како се наиђу, крећући се с лева на десно у датом низу.
Још један вектор одозго, са својим текућим укупним вредностима, налази се у овој табели:
Постоје две секвенце са максималним сумама. Они су {10, 15, 9}, што даје збир од 34; и {4, 6, 3, 2, 8, 3} што даје збир од 26. Секвенца која даје збир од 34 је оно што се жели.
Приметите да за текуће укупне вредности постоје два врха који су вредности, 30 и 13. Ови врхови одговарају последњим индексима две секвенце.
Опет, идеја Каданеовог алгоритма је да ради текући зброј док пореди максималне суме како се наиђу, крећући се с лева на десно у датом низу.
Код по Каданеовом алгоритму у Ц++
Код дат у овом делу чланка није нужно оно што је Кадане користио. Међутим, то је по његовом алгоритму. Програм би, као и многи други Ц++ програми, почео са:
#инцлуде <иостреам>#инцлуде<вектор>
користећи простор имена стд;
Постоји укључивање иостреам библиотеке, која је одговорна за улаз и излаз. Користи се стандардни именски простор.
Идеја Каданеовог алгоритма је да има текући зброј док упоређује максималне суме како се наиђу, крећући се с лева на десно у датом низу. Функција за алгоритам је:
инт макСунАрраи ( вектор < инт > & А ) {инт Н = А.величина ( ) ;
инт макСум = А [ 0 ] ;
инт рунТотал = А [ 0 ] ;
за ( инт и = 1 ; и < Н; и++ ) {
инт темпРунТотал = рунТотал + А [ и ] ; // може бити мањи од А [ и ]
ако ( А [ и ] > темпРунТотал )
рунТотал = А [ и ] ; // ин случај А [ и ] је већи од текућег укупног
друго
рунТотал = темпРунТотал;
ако ( рунТотал > макАмоунт ) // упоређујући све максималне суме
макСум = рунТотал;
}
повратак макАмоунт;
}
Одређује се величина, Н датог низа (вектора). Променљива, макСум је једна од могућих максималних сума. Низ има најмање један максимални збир. Варијабла рунТотал представља текући збир у сваком индексу. Оба су иницијализована првом вредношћу низа. У овом алгоритму, ако је следећа вредност у низу већа од текућег укупног, та следећа вредност ће постати нови текућа укупна вредност.
Постоји једна главна фор-петља. Скенирање почиње од 1 а не од нуле због иницијализације променљивих, макСум и рунТотал до А[0] који је први елемент датог низа.
У фор-петљи, прва изјава одређује привремени текући збир додавањем тренутне вредности акумулираном збиру свих претходних вредности.
Затим, постоји конструкција иф/елсе. Ако је само тренутна вредност већа од текућег укупног до сада, тада та појединачна вредност постаје текућа укупна. Ово је згодно посебно ако су све вредности у датом низу негативне. У овом случају, највећа негативна вредност ће постати максимална вредност (одговор). Ако само тренутна вредност није већа од привременог текућег укупног до сада, тада текући збир постаје претходни текући збир плус тренутна вредност, – ово је други део конструкције иф/елсе.
Последњи сегмент кода у фор-петљи бира између било ког претходног максималног збира за претходни низ (подниз) и било којег тренутног максималног збира за тренутни низ. Стога се бира већа вредност. Може постојати више од једне максималне суме подниза. Имајте на уму да би текући збир могао расти и падати, пошто се низ скенира с лева на десно. Пада како испуњава негативне вредности.
Коначна изабрана максимална сума подниза се враћа након фор-петље.
Садржај за одговарајућу Ц++ главну функцију, за Каданеову алгоритамску функцију је:
вектор < инт > А = { 5 , - 7 , 3 , 5 , - два , 4 , - 1 } ; // { 3 , 5 , - два , 4 } - > 10инт рет1 = макСунАрраи ( А ) ;
цоут << рет1 << ендл;
вектор < инт > Б = { - два , 1 , - 3 , 4 , - 1 , два , 1 , - 5 , 4 } ; // { 4 , − 1 , два , 1 } - > 6
инт рет2 = макСунАрраи ( Б ) ;
цоут << рет2 << ендл;
вектор < инт > Ц = { 3 , два , - 6 , 4 , 0 } ; // { 3 , два } - > 5
инт рет3 = макСунАрраи ( Ц ) ;
цоут << рет3 << ендл;
вектор < инт > Д = { 3 , два , 6 , - 1 , 4 , 5 , - 1 , два } ; // { 3 , два , 6 , - 1 , 4 , 5 , - 1 , два } - > 5
инт рет4 = макСунАрраи ( Д ) ;
цоут << нет4 << ендл;
вектор < инт > Е = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , петнаест , 4 , - 8 , - петнаест , - 22 } ; // { 6 , 5 , 10 , - 5 , петнаест , 4 } - > 35
инт рет5 = макСунАрраи ( И ) ;
цоут << рет5 << ендл;
вектор < инт > Ф = { - 4 , 10 , петнаест , 9 , - 5 , - двадесет , - 3 , - 12 , - 3 , 4 , 6 , 3 , два , 8 , 3 , - 5 , - два } ; // { 10 , петнаест , 9 } - > 3. 4
инт рет6 = макСунАрраи ( Ф ) ;
цоут << десно 6 << ендл;
Уз то, излаз ће бити:
10
6
5
двадесет
35
3. 4
Свака линија одговора овде одговара датом низу, по реду.
Закључак
Временска сложеност за Каданеов алгоритам је О(н), где је н број елемената у датом низу. Ова временска сложеност је најбржа за проблем максималног подниза. Постоје и други алгоритми који су спорији. Идеја Каданеовог алгоритма је да ради текући зброј, док пореди максималне суме како се наиђу, крећући се с лева на десно у датом низу. Ако је само тренутна вредност већа од текућег укупног до сада, тада та појединачна вредност постаје нови текући збир. У супротном, нови текући збир је претходни текући збир плус тренутни елемент, као што је предвиђено, док се дати низ скенира.
Може постојати више од једног максималног збира, за различите могуће поднизе. Бира се највећи максимални збир за све могуће поднизе.
Који су гранични индекси за опсег изабраног максималног збира? – То је расправа за неки други пут!
Цхрис