Что-то я затянул с ответами на вопросы с собеседования в 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). Этой замечательной книги, к сожалению, сейчас нет в продаже. Найти ее можно только в электронном виде (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[i], 0);
		
		

			
                maxSoFar = Math.Max(maxSoFar, maxEndingHere);
		
		

			
            }
		
	

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

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

Понравился пост? Подпишись на RSS, чтобы не пропустить новые интересные материалы.