Алгоритм Каденса: непрерывный подмассив наибольшей суммы

Какова наибольшая сумма непрерывного подмассива?

Подмассив — это непрерывная часть массива. Это может быть отдельный элемент массива или некоторая часть массива. Смежный подмассив с наибольшей суммой означает подмассив, который имеет максимальное значение суммы.

Например, массив имеет вид {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Его подмассивы могут быть: {-10,5,1,6} или {5,1,6} или {2,7,3, -5} и т. д. Но {5,1,6,3} не может быть подмассив, потому что они не поддерживают последовательности.

Если вы заметили, что среди всех подмассивов следующий выделенный подмассив (5,1,6) имеет максимальное значение суммирования:

Сумма подмассива {5,1,6} = 11 — это максимальная сумма во всех возможных комбинациях подмассива вышеуказанного массива. Итак, для приведенного выше массива максимальный подмассив равен {5,1,6}.

Алгоритм Каденса: непрерывный подмассив наибольшей суммы

Простой подход к решению непрерывного подмассива наибольшей суммы

Простой способ решить эту проблему — использовать два цикла для поиска всех подмассивов, вычисления суммы и затем нахождения ее максимального значения.

Вот блок-схема простого подхода к поиску непрерывного подмассива наибольшей суммы. Это грубый подход, поскольку мы перебираем все возможные подмассивы.

Вот простые шаги, чтобы сделать это.

Шаг 1) Инициализируйте max_sum минимальным целочисленным значением и присвойте переменным «begin» и «end» ноль.

Шаг 2) Пусть i и j — индекс массива, где «j» больше, чем равно «i». Он представляет начальный индекс подмассива, а «j» представляет конечный индекс подмассива.

Шаг 3) «Current_sum» будет содержать сумму подмассива. После расчета текущей суммы проверьте, превышает ли current_sum максимальную_сумму.

Шаг 4) Если текущая_сумма больше, замените максимальную_сумму текущей суммой.

Шаг 5) Проверьте, достигает ли «j» конца массива или нет. Если «j» достигает конца массива, увеличьте «i» и измените значение current_sum на 0.

Шаг 6) Выполняйте все эти шаги, пока «i» не достигнет конца массива.

Шаг 7) В конце этих двух циклов max_sum будет содержать наибольшую сумму подмассива.

Псевдокод для простого подхода

  function maximumSubarraySum():
    input: array
  for all possible subArray from array:
    calculate sum of each sub array
    store the maximum subArray
  return the maximum sum

C++ Реализация простого подхода

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
  int max_sum = -1e9;
  int begin = 0;
  int end = 0;
  for (int i = 0; i < n; i++) {
    int current_sum = 0;
    for (int j = i; j < n; j++) {
      current_sum += array[j];
      if (max_sum < current_sum) {
        max_sum = current_sum;
        begin = i;
        end = j;
      }
    }
  }
  cout << "largest sum is " << max_sum << endl;
  cout << "largest sum contiguous subarray: ";
  for (int i = begin; i <= end; i++) {
    cout << array[i] << "\t";
  }
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Вывод:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Реализация простого подхода

def maximumSubarraySum(numbers):
max_sum,begin,end = -1e9, 0 , 0
  for i in range(len(numbers)):
    current_sum=0
  for j in range(i,len(numbers)):
    current_sum+=numbers[j]
  if max_sum<current_sum:
    max_sum=current_sum
  begin,end=i,j
    print("largest sum is ",max_sum)
    print("largest sum contiguous subarray: ",end="")
  for i in range(begin,end+1):
    print(numbers[i],end='\t')
    numbers = [-10,5,1,6,-9,2,-7,3,-5]
    maximumSubarraySum(numbers)

Вывод:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Алгоритм Кадане для поиска непрерывного подмассива наибольшей суммы

Алгоритм Кадане — это разновидность метода «динамического программирования». Здесь мы будем использовать один цикл вместо двух. Общая реализация алгоритма Кадане работает только для массивов положительных чисел.

Нам нужны только две переменные, чтобы найти непрерывный подмассив наибольшей суммы. Вот блок-схема алгоритма Кадане:

Вот шаги алгоритма Кадане:

Шаг 1) Создайте две переменные: current_sum и max_sum.

«Current_sum» сохранит значение максимальной суммы, которая заканчивается определенным индексом массива, а «max_sum» сохранит максимальное значение суммирования на данный момент.

Шаг 2) Мы добавим значение с current_sum для каждого элемента массива. Затем мы проверим два условия ниже:

• Если current_sum меньше текущего элемента, то значение current_sum будет текущим элементом.
• Если max_sum меньше current_sum, то max_sum будет равно current_sum.

Шаг 3) Выполнив предыдущий шаг для всего массива, мы получим наибольшую сумму непрерывного подмассива в переменной «max_sum».

Пример алгоритма Кадане

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

Предположим, что данный массив имеет следующий вид:

Вот шаги алгоритма Кадане:

Шаг 1) Создайте две переменные: current_sum и max_sum. Назначьте INT_MIN для max_sum и ноль для current_sum. (Здесь INT_MIN означает минимальное целое число).

Шаг 2) По индексу 0 значение равно 4. Итак, current_sum = 0 + 4 или 4. Здесь current_sum больше max_sum, max_sum будет 4.

Шаг 3) В индексе 1 значение равно -2. Итак, текущая_сумма = 4 + (-2) или 2.

На этот раз current_sum меньше max_sum. В результате значение max_sum не будет обновлено.

Шаг 4) Следующее значение — 1. Если мы добавим его к current_sum, то current_sum будет равно 3. Тем не менее, max_sum больше, чем current_sum. Таким образом, max_sum не будет обновляться.

Шаг 5) В индексе 3 значение равно трем. Мы обновим значение, увеличив current_sum на 3. Таким образом, current_sum будет равно 6.

В этом случае max_sum меньше текущей_суммы. Таким образом, max_sum будет обновлен значением current_sum.

Шаг 6) Для последнего элемента массива мы имеем -1. Если мы добавим это к current_sum, current_sum будет равно 5, что меньше max_sum. Таким образом, max_sum останется равным 6.

Когда мы достигли конца массива, алгоритм на этом заканчивается. Теперь «max_sum» содержит подмассив максимальной суммы. Это 5. Подмассив равен {4,-2,1,3}.

Псевдокод алгоритма Кадане

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each elements in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++Реализация алгоритма Кадане

#include < iostream >
using namespace std;
void kadane(int array[], int n) {
  int current_sum = 0;
  int max_sum = -1e9;
  // -1e9 means -10000000
  for (int i = 0; i < n; i++) {
    current_sum += array[i];
    if (max_sum < current_sum) {
      max_sum = current_sum;
    }
    if (current_sum < array[i]) {
      current_sum = array[i];
    }
  }
  cout << "largest sum is " << max_sum << endl;
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  kadane(array, sizeof(array) / sizeof(array[0]));
}

Вывод:

largest sum is 12

Python Реализация алгоритма Кадане

def kadane(numbers):
  current_sum = 0
  max_sum = -1e9
for i in range(len(numbers)):
  current_sum += numbers[i]
if max_sum < current_sum:
  max_sum = current_sum
if current_sum<numbers[i]:
  current_sum = numbers[i]
  print("largest sum is ",max_sum)
  kadane([-10,5,1,6,-9,2,-7,3,-5])

Вывод:

largest sum is 12

Анализ сложности для непрерывного подмассива наибольшей суммы

Простой подход использует два цикла. Этот метод вычисляет все возможные суммы подмассивов, чтобы найти наибольшую из них. Это подход грубой силы. Каждый цикл выполняется до конца массив.

Если в массиве всего N элементов, то с помощью двух циклов пройдем N² элементы. В результате временная сложность для простого подхода к поиску непрерывного подмассива с наибольшей суммой будет равна O(N2). Здесь «О» означает функцию сложности.

С другой стороны, алгоритм Кадане — это метод динамического программирования, позволяющий найти подмассив максимальной непрерывной суммы. Если вы последуете примеру или коду, вы увидите, что мы используем только один цикл.

В результате, если входной массив имеет размер N, то временная сложность алгоритма Кадане будет равна O(N). Это быстрее, чем простой подход. Например, массив, содержащий 100 элементов. Простой подход потребует 100*100 или 10,000 100 процессорного времени. Но алгоритм Кадане потребует всего XNUMX процессорного времени.