DeveloperGuru.NET — гуру-программист в Сети Блог о Web, SEO и партнерских программах
Что-то я затянул с ответами на вопросы с собеседования в 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). Этой замечательной книги, к сожалению, сейчас нет в продаже. Найти ее можно только в электронном виде.
Приведу реализацию алгоритма из книги на C#:
|
1 2 3 4 5 6 7 8 9 10 11 |
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[i], 0); maxSoFar = Math.Max(maxSoFar, maxEndingHere); } |
В этом примере вычисляется только максимальная сумма, без определения индексов m,k. Заменив методы Max на конструкции if … else с запоминанием индексов, несложно найти m и k.
Ключевой момент этого алгоритма заключается в том, что любой положительный подвектор массива увеличивает максимальную сумму.
