Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 20
Текст из файла (страница 20)
Нам все равно нужно проверить 1" ) = Н(пз) подмассивов в случае периода из п дней. В упр. 4.1.2 требуется показать, что хотя вычисление стоимости одного подмассива может потребовать времени, пропорционального длине этого подмас- ! 2 3 4 5 б 7 8 9 !О 7! 72 !3 !4 !5 зб А ГО~-,'3)-2$(ГЗО -'.3~.!6(-'23),!б:~2гбл!-'"'7-'~~Я-.ЗХ ~~ЛЗ',":4 ~,7" Максимальный подмассив Рнс. 4З. Изменения цен как входные данные для задачи поиска максимального подмассива.
Здесь подмассив А(8 .. 1Ц с суммой 43 имеет наибольшую сумму срс!ш всех непрерывных подмасснвов массива А. ))зава 4. разздвллй и властвуй Решеяяе "разделяй и властвуй" Давайте подумаем о том, как можно решить задачу поиска максимального подмассива с использованием метода "разделяй и властвуй".
Предположим, что мы хотим найти максимальный подмассив подмассива А[[ею .. ЬздЬ]. Технология "разделяй и властвуй" предполагает, что мы делим массив на две части, по возможности одинакового размера, т.е. мы находим среднюю точку подмассива, скажем, пзЫ, и рассматриваем подмассивы А[[опз .. тЫ] и А[тЫ + 1 .. ЬздЬ].
Как показано на рис.4.4,(а), любой непрерывный подмассив А[а..у] массива А[[сиз .. ЬздЬ] должен находиться только в одном нз следующих положений: полностью располагаться а подмассиве А[[сиз .. пзЫ], так что [опз < з' < у < тпЫ; полностью располагаться в подмассиве А[тиЫ + 1 .. ЬздЬ], так что тЫ < з < ) < ЬздЬ; ° пересекать среднюю точку, так что [озл < з < тЫ < ) < ЬздЬ. Следовательно, максимальный подмассив массива А[[ою..ЬздЬ] должен располагаться ровно одним из этих способов. Фактически максимальный подмассив массива А[[сиз.. ЬздЬ] должен иметь наибольшую сумму среди всех ыул Павкктью в А[Лзш..
шЫ) Полностью вА[тЫ+! ..Ну (а) 1 ' +'-л л) А[з.. тЫ) (б) Рис. 4.4. (а) Возможные размещения подмассивов массива А[[ош .. Лзул[: полностью в А[йзш., зли)[, полносп ю в А[тзз[+ 1 .. Лзул[ нли с пересечением средней точки злы. (6) Любой пццмазшив массива А[)ош .. Лзул[, пересекающий среднюю точку, содержит два ппцмасснва А[я .. пиа[ и А[ты+ 1 ..1[, где лзш < з < озы и пззз) < з < лзул. сина, при вычислении всех е)(п ) сумм подмассивов можно организовать вычисления таким образом, что каждый подмассив с учетом уже вычисленных ранее сумм подмассивов будет вычисляться за время О(1), Таким образом, решение методом грубой силы потребует ез(пз) времени. Так что давайте поищем более эффективное решение задачи максимального подмассива.
Говоря о максимальном подмассиве в единственном числе, следует отдавать себе отчет в том, что таких подмассивов, сумма элементов которых достигает маюимального значения, может быть несколько. Задача поиска максимального подмассиаа интересна толью в том случае, когда массив содержит некоторое количество отрицательных значений. Если же все элементы массива положительны, то задача поиска максимального подмассива становится тривиальной, так как в этом случае наибольшую сумму имеет весь массив целиком. 96 Часть д Основы подмассивов, полностью находящихся в А[1ото .. тЫ], полностью находящихся в А[тЫ+ 1 ..
ЬтдЬ] или пересекающих среднюю точку. Максимальные подмассивы А[1ото .. тЫ] и А[тЫ+ 1 .. Ь1дЬ] можно найти рекурсивно, поскольку эти две подзадачи представляют собой экземпляры задачи поиска максимального подмассива меньшего размера, Таким образом, все, что осталось сделать, — это найти максимальный подмассив, пересекающий среднюю точку, и выбрать нз этих трех подмассивов тот, у которото будет наибольшая сумма. Можно легко найти максимальный подмассив, пересекающий среднюю точку, за время, линейно зависящее от размера подмассива А[1ово .. Ь1дЬ].
Эта задача не является меньшим экюмпляром нашей исходной задачи, поскольку при этом добавлено ограничение, что подмассив должен пересекать среднюю точку. Как показано на рис.4.4,(б), любой подмассив, пересекающий среднюю точку, состоит из двух подмассивов А[1 .. тЫ] и А[тЫ+ 1 .. т], где 1ово < 1 < тЫ и тЫ < т' < ЬтдЬ. Следовательно, нужно просто найти максимальные подмассивы вида А[1 .. тЫ] н А[тЫ + 1.. 1], а затем объединить их. Процедура Рпчп-МАх-Скоззтмо-Бттвлккм' получает в качестве входных данных массив А и индексы 1отв, тЫ и МдЬ, и возвращает кортеж, содержащий индексы, определяющие пересекающий среднюю точку максимальный подмассив, а также сумму значений элементов этого максимального подмассива. Р!тР-МАх-Ск0$зпч6-811ВАккАУ(А, 1отв, тЫ, Ь)дЬ) 1 1е11-вит = — оо 2 вит=О 3 1ог 1 = тЫ дотгпто 1ою 4 вита = вит+ А[1] 5 11 вит > 1е7т-вит б 1е72-вит = вит 7 тах-1е7т = 1 8 пдЬ8-вит = — оо 9 вит=О 10 1ог т' = тЫ+11о МдЬ 11 вит = вит+ А[1] 12 !Г вит > тщЫ-вит 13 г1дЬ1-вит = вит 14 тах-г1дют = т 15 гегпгп (тах-1еЯ, тах-гтдЫ, 1е72-вит + тъдИ-вит) Эта процедура работает следующим образом.
Строки 1-7 находят максимальный подмассив в левой половине, А[1отс .. тЫ]. Поскольку этот подмассив должен содержать А[тЫ], цикл 1ог в строках 3-7 начинает работу со значения индекса 1, равного тюЫ, и идет вниз до значения 1отв, так что каждый рассматриваемый подмасснв имеет вид А[1 .. тЫ]. В строках 1 и 2 выполняется инициализация переменной 1е72-вит, в которой хранится наибольшая найденная к этому моменту сумма, и вит, хранящей сумму элементов в А[1 .. тЫ].
Когда в строке 5 мы находим подмассив А[1 .. тЫ] с суммой значений, большей, чем 1е7т-вит, мы об- 97 Рваяа К Раэдяяяй и властвуй новляем значение переменной 1е/Г-вит, делая его равным этой сумме в строке б, а в строке 7 мы обновляем переменную тах-1е/1, записывая в нее индекс э. Строки 8 — 14 аналогично работают в правой половине, А[тЫ+1 .. ЬэдЬ].
Здесь цикл Гог в строках 10-14 начинает работу со значения индекса у, равного тЫ + 1, и идет вверх до значения МдЬ, так что каждый рассматриваемый подмассив имеет вид А[тЫ+1 ..Я. Наконец строка 15 возвращает индексы тах-1е/1 и тах-этдЫ, которые определяют максимальный подмассив, пересекающий среднюю точку, вместе с суммой 1е/1-яит + г1уИ-яит значений в подмассиве А [тах-1еЯ ..
тах-гэдЫ[. Если подмассив А[1ош .. ЬэдЬ[ содержит и элементов (так что п = Ь1дЬ вЂ” 1ош+ 1), мы утверждаем, что вызов Р1мп-МАх-СкоззпчО-Б11ВАккАу(А, 1ош, тЫ, ЬГдЬ) выполняется за время еэ(п). Поскольку каждая итерация каждого из двух циклов Гог требует тв(1) времени, нужно просто подсчитать, сколько всего итераций выполняется. Цикл Гог в строках 3-7 выполняет тЫ вЂ” 1ош + 1 итераций, а цикл Гог в строках 10-14 — Ь1дЬ вЂ” тЫ итераций, так что общее количество итераций равно (тЫ вЂ” 1ош+ 1) + (МдЬ вЂ” тЫ) = ЬэуЬ вЂ” 1ош+ 1 Имея процедуру Рпчп-МАХ-Скоззпчп-Б11ВАККАу с линейным временем работы, можно записать псевдокод алгоритма "разделяй и властвуй*', решающего задачу поиска максимального подмассива.
Р!ВВ-МАх!мам-Б11ВАккАУ(А, 1ош, ЬэдЬ) 1 1Г ЬэуЬ == 1ош 2 генэгп (1ош, ЬэдЬ, А[1ош[) // Базовый случай: // только один элемент 3 е1ве тЫ = [(1ош+ ЬэуЬ)/21 4 (1е/1-1ош, 1е/Г-ЬэдЬ, 1е/1-вит) = Рцчп-МАх!м11м-БУВАккАУ(А, 1ош, тЫ) 5 (пуЫ-(ош, гэдЬГ-ЬэдЬ, гяур-яит) = Р1ХП-МАХ1М11М-Б11ВАККАУ(А, тЫ + 1, МдЬ) б (ставя-1ош, ставя-ЬэуЬ, сговв-вит) = Рцчп-МАХ-Скозз11чс-Б11ВАккАу(А, 1ош, тЫ, ЬГдЬ) 7 1Г 1е/Г-яит > гэдЫ-яит и 1е/1-вит > сгояв-вит 8 генэгп (!еЯ-1ош, 1е/1-Ь(уЬ, 1е/1-вит) 9 е!ве1Г этдЫ-вит > 1е/1-вит и этдЫ-вит > егозя-яит 1О геиэгп (г1дЫ-(ош, тъдЫ-ЬэдЬ, тъдЫ-яит) 11 е1ве гегпгп (ставя-1ош, ставя-Му1э, стаяв-яит) Начальный вызов Рпчп-МАХ1М11М-Б11ВАккАу(А, 1, А. 1епдгЬ) находит максимальный подмассив массива А[1 ..
и[. Подобно процедуре Рпчп-МАх-Скоззпчо-Б11ВАккАу, рекурсивная процедура Рпчп-МАх1М11м-Б11ВАккАу возвращает кортеж, состоящий из индексов, определяющих максимальный подмассив, и суммы значений этого максимального подмассива. В строке 1 выполняется проверка базового случая — когда подмассив я ээь ээээ Часть 8 Основы 98 состоит только из одного элемента. Подмассив с единственным элементом имеет только один подмассив — себя, так что строка 2 возвращает кортеж с начальным и конечным индексами для единственного элемента вместе с его значением.
Строки 3-11 обрабатывают рекурсивный случай. Строка 3 выполняет разделение, вычисляя индекс гпЫ средней точки. Будем называть подмассив А[1ова .. тЫ[ леваки ивдмиссиввм, а А[тЫ + 1 .. йод)ь[ — лривым ивдмиссиввм. Поскольку мы знаем, что подмассив А[1ова .. )вада[ содержит как минимум два элемента, и левый, и правый подмассивы содержат хотя бы по одному элементу. Строки 4 и 5 "властвуют", рекурсивно находя максимальные подмассивы в левом и правом подмассивах соответственно. Строки 6-11 образуют часть комбинирования. В строке 6 выполняется поиск максимального подмассива, который пересекает среднюю точку. (Вспомним, что, поскольку в строке 6 решается подзадача, не являющаяся экземпляром меньшего размера исходной задачи, мы рассматриваем ее как входящую в часть комбинирования.) В строке 7 выполняется проверка, содержится ли максимальный подмассив в левом подмассиве, и если содержится, то строка 8 возвращает его.
В противном случае строка 9 проверяет наличие максимального подмассива в правом подмассиве, а строка 10 возвращает его. Если же ни левый, ни правый подмассивы не содержат подмассива с максимальной суммой, то последний должен пересекать среднюю точку, и он возвращается в строке 11. Анализ алгоритма "разделяй и властвуй" Теперь запишем рекуррентное соотношение, которое описывает время работы рекурсивной процедуры Е1нп-МАх1мцм-Зцвлккм'. Как и в ходе анализа сортировки слиянием в разделе 2.3.2, сделаем упрощающее допущение о том, что размер исходной задачи представляет собой степень 2, так что размеры всех подзадач — целые числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
