Проблема максимального подмассива в C++

Problema Maksimal Nogo Podmassiva V C



Задача о максимальном подмассиве аналогична задаче о максимальном срезе. В этом руководстве обсуждается проблема с программированием на C++. Возникает вопрос: какова максимальная сумма любой возможной последовательности последовательных чисел в массиве? Это может означать весь массив. Эта проблема и ее решение на любом языке называются проблемой максимального подмассива. Массив может иметь возможные отрицательные числа.

Решение должно быть эффективным. Он должен иметь самую быструю временную сложность. На данный момент самый быстрый алгоритм решения известен в научном сообществе как алгоритм Кадане. В этой статье объясняется алгоритм Кадане с C++.







Примеры данных

Рассмотрим следующий вектор (массив):



вектор < инт > А = { 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 , - 20 , - 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. Эти пики соответствуют последним индексам двух последовательностей.

Опять же, идея алгоритма Кадане состоит в том, чтобы подсчитывать промежуточные суммы, сравнивая максимальные суммы по мере их появления, двигаясь слева направо в заданном массиве.

Код с помощью алгоритма Кадане на C++

Код, приведенный в этом разделе статьи, не обязательно является тем, что использовал Кадане. Но это по его алгоритму. Программа, как и многие другие программы на C++, начиналась бы так:

#include <иопоток>
#include<вектор>


использование пространства имен std;

Есть включение библиотеки iostream, отвечающей за ввод и вывод. Используется стандартное пространство имен.

Идея алгоритма Кадане состоит в том, чтобы иметь промежуточный итог при сравнении максимальных сумм по мере их появления, перемещаясь слева направо в заданном массиве. Функция для алгоритма:

int maxSunArray ( вектор < инт > & А ) {
int N = A.размер ( ) ;

интервал максСумм = А [ 0 ] ;
int runTotal = А [ 0 ] ;

за ( инт я знак равно 1 ; я < Н; я++ ) {
int tempRunTotal = runTotal + A [ я ] ; // может быть меньше А [ я ]
если ( А [ я ] > tempRunTotal )
общий итог = А [ я ] ; // в кейс А [ я ] больше, чем нарастающая сумма
еще
общий пробег = временный общий итог;

если ( runTotal > макссумма ) // сравнивая все максимальные суммы
максимальная сумма = общая сумма;
}

возвращаться максимальное количество;
}


Определяется размер N заданного массива (вектора). Переменная maxSum является одной из возможных максимальных сумм. Массив имеет по крайней мере одну максимальную сумму. Переменная runTotal представляет промежуточный итог по каждому индексу. Они оба инициализируются первым значением массива. В этом алгоритме, если следующее значение в массиве больше промежуточного итога, то это следующее значение станет новым промежуточным итогом.

Есть один основной цикл for. Сканирование начинается с 1, а не с нуля из-за инициализации переменных maxSum и runTotal значением A[0], которое является первым элементом данного массива.

В цикле for первый оператор определяет временную промежуточную сумму, добавляя текущее значение к накопленной сумме всех предыдущих значений.

Далее идет конструкция if/else. Если только текущее значение больше промежуточной суммы на данный момент, то это единственное значение становится промежуточной суммой. Это удобно, особенно если все значения в данном массиве отрицательные. В этом случае максимальным значением (ответом) станет только самое высокое отрицательное значение. Если только текущее значение пока не больше, чем временная промежуточная сумма, то промежуточная сумма становится суммой предыдущей промежуточной суммы плюс текущее значение — это часть else конструкции if/else.

Последний сегмент кода в цикле for выбирает между любой предыдущей максимальной суммой для предыдущей последовательности (подмассива) и любой текущей максимальной суммой для текущей последовательности. Поэтому выбирается более высокое значение. Может быть более одной максимальной суммы подмассива. Обратите внимание, что промежуточная сумма будет увеличиваться и уменьшаться, поскольку массив сканируется слева направо. Он падает, когда встречается с отрицательными значениями.

Окончательная выбранная максимальная сумма подмассива возвращается после цикла for.

Содержимое подходящей основной функции C++ для функции алгоритма Кадане:

вектор < инт > А = { 5 , - 7 , 3 , 5 , - два , 4 , - 1 } ; // { 3 , 5 , - два , 4 } - > 10
int ret1 = maxSunArray ( А ) ;
cout << рет1 << конец;

вектор < инт > Б = { - два , 1 , - 3 , 4 , - 1 , два , 1 , - 5 , 4 } ; // { 4 , − 1 , два , 1 } - > 6
int ret2 = maxSunArray ( Б ) ;
cout << рет2 << конец;

вектор < инт > С = { 3 , два , - 6 , 4 , 0 } ; // { 3 , два } - > 5
int ret3 = maxSunArray ( С ) ;
cout << рет3 << конец;

вектор < инт > Д = { 3 , два , 6 , - 1 , 4 , 5 , - 1 , два } ; // { 3 , два , 6 , - 1 , 4 , 5 , - 1 , два } - > 5
int ret4 = maxSunArray ( Д ) ;
cout << сеть4 << конец;

вектор < инт > Э = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , пятнадцать , 4 , - 8 , - пятнадцать , - 22 } ; // { 6 , 5 , 10 , - 5 , пятнадцать , 4 } - > 35
int ret5 = maxSunArray ( А ТАКЖЕ ) ;
cout << рет5 << конец;

вектор < инт > Ф = { - 4 , 10 , пятнадцать , 9 , - 5 , - 20 , - 3 , - 12 , - 3 , 4 , 6 , 3 , два , 8 , 3 , - 5 , - два } ; // { 10 , пятнадцать , 9 } - > 3. 4
int ret6 = maxSunArray ( Ф ) ;
cout << справа 6 << конец;


При этом вывод будет:

10

6

5

20

35

3. 4

Каждая строка ответа здесь соответствует заданному массиву по порядку.

Вывод

Временная сложность алгоритма Кадане равна O(n), где n — количество элементов в заданном массиве. Эта временная сложность является самой быстрой для задачи максимального подмассива. Есть и другие алгоритмы, которые работают медленнее. Идея алгоритма Кадане состоит в том, чтобы подсчитывать промежуточные суммы, сравнивая максимальные суммы по мере их появления, двигаясь слева направо в заданном массиве. Если только текущее значение больше промежуточного итога на данный момент, то это единственное значение становится новым промежуточным итогом. В противном случае новая промежуточная сумма представляет собой предыдущую промежуточную сумму плюс текущий элемент, как и ожидалось, при сканировании данного массива.

Может быть более одной максимальной суммы для различных возможных подмассивов. Выбирается наибольшая максимальная сумма для всех возможных подмассивов.

Каковы предельные показатели для диапазона выбранной максимальной суммы? – Это разговор в другой раз!

Крис