Тесты при приеме на работу в ABBYY Software – Ответы 2

Что-то я затянул с ответами на вопросы с собеседования в ABBYY. Да и вообще, давно ничего не писал в блоге. Надо срочно исправляться.

Сегодня рассмотрим вторую задачу:

2. Дан массив a[1],..a[N].. найти m,k (m<k) такие что a[m] + ..+a[k] — максимальна. Сложность алг-ма = N.

Вообще-то, не зная заранее решения, найти алгоритм, работающий за время O(N), в течение короткого времени (на собеседовании) довольно сложно. Те же, кто это действительно могут, работают не в ABBYY. Гораздо более полезное собеседование можно провести, убрав требование быстродействия O(N). Нетрудно написать алгоритм работающий со скоростью O(N³). Далее, легко его оптимизировать до O(N²). На этом этапе можно многое узнать о сообразительности кандидата. Используя подсказки, можно прийти к алгоритму O(N log N). Лично я именно так проводил бы собеседование, основанное на этой задаче.

Что касается решения O(N), то оно, наряду с другими вариантами, прекрасно описано в книге Джона Бентли “Жемчужины программирования” (глава 7). Этой замечательной книги, к сожалению, сейчас нет в продаже. Найти ее можно только в электронном виде.

Приведу реализацию алгоритма из книги на C#:

В этом примере вычисляется только максимальная сумма, без определения индексов m,k.  Заменив методы Max на конструкции if … else с запоминанием индексов, несложно найти m и k.

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