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

инициализировать std vector в C++ с примерами Программирование и разработка

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

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

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

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

vector<int> A = {5, —735, —24, —1};

Срез (подмассив) с максимальной суммой — это последовательность {3, 5, −2, 4}, которая дает сумму 10. Никакая другая возможная последовательность, даже весь массив, не даст суммы до значение 10. Весь массив дает сумму 7, которая не является максимальной суммой.

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

vector<int> B = {21, —34, —121, —54};

Срез (подмассив) с максимальной суммой — это последовательность {4, −1, 2, 1}, которая дает в сумме 6. Обратите внимание, что в подмассиве могут быть отрицательные числа для максимальной суммы.

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

vector<int> C = {32, —64};

Срез (подмассив) с максимальной суммой — это последовательность {3, 2}, которая дает в сумме 5.

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

vector<int> D = {326, —145, —12};

Подмассив с максимальной суммой — это последовательность {3, 2, 6, −1, 4, 5, −1, 2}, которая дает в сумме 20. Это весь массив.

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

vector<int> E = {57, —4, —10, —66510, —5154, —8, —15, —22};

Здесь есть два подмассива с максимальными суммами. Более высокая сумма — это та, которая считается решением (ответом) для задачи о максимальном подмассиве. Подмассивы: {5, 7} с суммой 12 и {6, 5, 10, −5, 15, 4} с суммой 35. Конечно, срез с суммой 35 ответ.

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

vector<int> F = {410159, —5, —20, —3, —12, —3463283, —5, —2};

Есть два подмассива с максимальными суммами. Более высокая сумма — это та, которая рассматривается как решение задачи о максимальном подмассиве. Подмассивы: {10, 15, 9} с суммой 34 и {4, 6, 3, 2, 8, 3} с суммой 26. Конечно, срез с суммой 34 ответ, потому что проблема состоит в том, чтобы искать подмассив с наибольшей суммой, а не подмассив с более высокой суммой.

Разработка алгоритма Кадане

Информация в этом разделе руководства не является оригинальной работой Кадане. Это собственный способ автора обучать алгоритму Кадане. Один из приведенных выше векторов с его промежуточными суммами находится в этой таблице:

Данные 5 7 -4 -10 -6 6 5 10 -5 15 4 -8 -15 -22
Общая сумма 5 12 8 -2 -8 -2 3 13 8 23 27 21 16 -6
индекс 1 2 3 4 5 6 7 8 9 10 11 12 13
Читайте также:  Java или JavaScript: тщательное сравнение

Промежуточный итог для индекса — это сумма всех предыдущих значений, включая значение индекса. Здесь есть две последовательности с максимальными суммами. Это {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 <iostream>
#include<vector>

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

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

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

    int maxSunArray(vector<int> &A) {
int N = A.size();

int maxSum = A[];
int runTotal = A[];

for (int i=1; i < N; i++) {
int tempRunTotal = runTotal + A[i];  //could be smaller than A[i]
if (A[i] > tempRunTotal)
runTotal = A[i];  //in case A[i] is bigger than running total
else
runTotal = tempRunTotal;

if (runTotal > maxSum)  //comparing all the maximum sums
maxSum = runTotal;
}

return maxSum;
}

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

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

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

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

Читайте также:  Как разделить строки на основе разделителя в C?

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

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

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

        vector<int> A = {5, —735, —24, —1};  //  {35, —24} —> 10
int ret1 = maxSunArray(A);
cout << ret1 << endl;

vector<int> B = {21, —34, —121, —54};  //  {4, −121} —> 6
int ret2 = maxSunArray(B);
cout << ret2 << endl;

vector<int> C = {32, —64};  //{32} —> 5
int ret3 = maxSunArray(C);
cout << ret3 << endl;

vector<int> D = {326, —145, —12};  //{326, —145, —12} —> 5
int ret4 = maxSunArray(D);
cout << ret4 << endl;

vector<int> E = {57, —4, —10, —66510, —5154, —8, —15, —22};  // {6510, —5154}>35
int ret5 = maxSunArray(E);
cout << ret5 << endl;

vector<int> F = {410159, —5, —20, —3, —12, —3463283, —5, —2};  // {10159}>34
int ret6 = maxSunArray(F);
cout << ret6 << endl;

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

10

6

5

20

35

34

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

Заключение

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

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

Оцените статью
bestprogrammer.ru
Добавить комментарий

Adblock
detector