Отправляет email-рассылки с помощью сервиса Sendsay

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

Подписаться Бесплатная новостная рассылка Подписчиков 2 RSS
  Март 2021   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: https://coding-interview-scrapbook.blogspot.com/
Открыта: 30-12-2019

Автор
Наталия

Статистика

2 подписчиков
0 за неделю
←   Все выпуски   →

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


Выпуск 4. Алгоритм Кадана

Здравствуйте, !
Задача. Дан (неотсортированный) массив с числами, нужно найти его непрерывный подмассив так, чтобы сумма чисел была максимальной среди всех возможных других подмассивов.

Пример. Показан на рисунке ниже.
Дан массив {-2, 1, -3, 4, -1, 2, 1, -5, 4}. Его максимальный непрерывыный подмассив выделен желтым маркером и состоит из чисел {4, -1, 2, 1}. Сумма этого подмассива равна 6 и это максимальное значение среди любых других непрерывных подмассивов даввного массива.

Решение в лоб.
Для каждого элемента массива считаем возможные непрерывные подмассивы, которые его содержат.
То есть, начинаем с числа -2. Сумма = -2.
Затем рассамтриваем подмассив {-2, 1}. Сумма = -1.
Затем рассамтриваем подмассив {-2, 1, -3}. Сумма  = -4.
...
Подмассив, который содержит весь массив от -2 до 4 (конец массива) суммарно дает 1.
Это мы обработали число 2.

Теперь стартуем с 1 (вторая ячейка).
Подмассив: {1, -3} в сумме = -2.
...
И так далее, пока не дойдём до подмассива от 1 до конца исходного массива.

И так далее.

Нетрудно заметить (нетрудно же?), что сложность этого алгоритма O(n^2).

Как можно сделать быстрее? Динамическое программирование в помощь!

Что такое "динамическое программирование"?

Источник: Как объяснить концепцию динамического программирования 4-летнему ребенку

*записывает"1+1+1+1+1+1+1+1 =" на листе бумаги*
"Чему это равно?"
*считает* "Восемь!"
*дописывает ещё одну "1+" слева*
"А теперь?"
*быстро отвечает* "Девять!"
"Как тебе удалось так быстро подсчитать, что это девять?"
"Просто добавил единичку (к восьми)"
"То есть тебе не пришлось пересчитывать, потому что ты помнил, что там было восемь! Динамическое програраммирование - это красивый способ назвать 'запомнить что-то, чтобы сэкономить время потом'"

Алгоритм Кадана 
Теперь посмотрим, как выглядел бы наш алгоритм "в лоб", если бы мы считали данные с конца массива. 

Мы берем последний элемент A[n-1] и считаем для него суммы массивов, которые заканчиваются в элеметах A[n-2], A[n-3], ..., A[0], как показано на рисунке:


 
А теперь рассмотрим подробнее элементы A[4]=-1 и A[5]=2. См. рисунок:

Из рисунка выше видно, что local_maximum[4] = 3 и это сумма подмассива [4, -1]. Зная local_maximum[4], нам не нужно подсчитывать суммы всех подмассивов, заканчивающихся в элементе A[5]. Нам достаточно рассмотреть подмассивы, отмеченные красной стрелочкой на рисунке выше, чтобы подсчитать  local_maximum[5].

И это приводит нас к принципу работы алгоритма Кадана.
local_maximum[i] = max(A[i], A[i]+local_maximum[i-1])

Таким образом, для каждого индекса i, задача сводится к тому, чтобы найти максимум ДВУХ чисел: A[i] и A[i]+local_maximum[i-1]. Учтём, что local_maximum[0] = A[0] (потому что на шаге i=0 мы рассматриваем только один элемент A[0]). Кроме того, нам достаточно одного прохода от 1 до A.length, чтобы решить задачу. И это, конечно, гораздо лучше, чем решение "в лоб", рассмотренное выше. Ибо сложность алгоритма в таком случае: O(n).

Имплементация алгоритма на Java:

     public static int kadaneValue(int[]matrix) {
        int local_maximum = matrix[0];
        int global_maximum = local_maximum;
       
        for (int i = 1; i < matrix.length; i++) {
            local_maximum = Math.max(matrix[i], matrix[i]+local_maximum);
            if (local_maximum>global_maximum) {
                global_maximum=local_maximum;
            }
        }
        return global_maximum;
    }

Обратите внимание, что вместо подсчёта массива local_maximum[i] мы используем одну переменную local_maximum, которую используем на каждой итерации i. А в переменной global_maximum мы запоминаем наибольшее встретившееся нам значение local_maximum. Итоговое значение global_maximum и будет результатом алгоритма.

 Вопросы, замечания, коментарии? Буду им рада.

С уважением,
Наталия Македа
natalia.macheda at gmail.com
2021-03-15, Trento

Внимание!
Письмо, которое вы мне отправите с вопросами и коментариями по тематике данной рассылки, может быть опубликовано полностью или частично в данной рассылке, если в нём нет явного запрета на это.

© Наталия Македа 2021.
Все материалы рассылки защищены авторским правом. Любая перепечатка или использование материалов рассылки в коммерческих целях возможна лишь с письменного согласия автора. При некоммерческом использовании ссылка на выпуск обязательна.
В избранное