Что-то я затянул с ответами на вопросы с собеседования в ABBYY. Да и вообще, давно ничего не писал в блоге. Надо срочно исправляться.
Сегодня рассмотрим вторую задачу:
2. Дан массив a[1],..a[N].. найти m,k (m<k) такие что a[m] + ..+a[k] — максимальна. Сложность алг-ма = N.
Вообще-то, не зная заранее решения, найти алгоритм, работающий за время O(N), в течение короткого времени (на собеседовании) довольно сложно. Те же, кто это действительно могут, работают не в ABBYY. Гораздо более полезное собеседование можно провести, убрав требование быстродействия O(N). Нетрудно написать алгоритм работающий со скоростью O(N3). Далее, легко его оптимизировать до O(N2). На этом этапе можно многое узнать о сообразительности кандидата. Используя подсказки, можно прийти к алгоритму O(N log N). Лично я именно так проводил бы собеседование, основанное на этой задаче.
Что касается решения O(N), то оно, наряду с другими вариантами, прекрасно описано в книге Джона Бентли “Жемчужины программирования” (глава 7). Этой замечательной книги, к сожалению, сейчас нет в продаже. Найти ее можно только в электронном виде (http://librus.ru/down.php?book=05753).
Приведу реализацию алгоритма из книги на C#:
| int[] a = { 1, 2, -2, 3, -5, 1, 1, 3}; |
| int N = a.Length; |
| int maxSoFar = 0; |
| int maxEndingHere = 0; |
| for(int i = 0; i < N; i++) |
| { |
| maxEndingHere = Math.Max(maxEndingHere + a, 0); |
| maxSoFar = Math.Max(maxSoFar, maxEndingHere); |
| } |
В этом примере вычисляется только максимальная сумма, без определения индексов m,k. Заменив методы Max на конструкции if … else с запоминанием индексов, несложно найти m и k.
Ключевой момент этого алгоритма заключается в том, что любой положительный подвектор массива увеличивает максимальную сумму.
Похожие посты:
