Разделяй и властвуй

Алгоритм быстрой сортировки (Quick sort algorithm)

Алгоритм быстрой сортировки - это алгоритм из серии "разделяй и властвуй", поэтому разобьем алгоритм на три части: разделение, властвование и комбинирование.

Для наглядности позначим сортируемый массив  А[p...r].

Разделение.

В этой части массив А[p...r] разбивается на две части, а именно на А[p...q-1] и А[q+1...r], где элементы А[p...q-1]  меньше или равно значению A[q], а элементы подмассива А[q+1...r] больше или равны значению A[q]. Где элемент q - вычисляется при исполнении процедуры разбиения.

Поис максимального подмассива

Задача: Поиск максимального подмассива

Существует множество задач, в которых нам нужно найти максимальный смежный подмассив внутри некоторого массива(который имеет хотя бы один елемент), который имеет наибольшую суму.

К примеру, дан массив [−2,1,−3,4,−1,2,1,−5,4], смежный подмасив [4,−1,2,1] имеет наибольшую суму равную 6.