Подмассив с максимальной суммой элементов

Опубликовано Nov 17, 2011 в Массивы и строки | 8 коммент.

, ,

Подмассив с максимальной суммой элементов

Дан массив чисел типа Integer 32. Числа могут быть как положительные, так и отрицательные.

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

Нужен алгоритм с линейной сложностью.

Дополнительный вопрос. Что можно предложить, если суммирование элементов подмассива заменить их перемножением?

C++
void find_subarray(const int* array, int array_size, int & begin, int & end)
{
  //ваш код
};
 
C#
static void FindSubarray(int[] array, out int begin, out int end)
{
//ваш код
}

Критерии оценки

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

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

const int size = 15;
int[] arr = { 1110, 2, 6, -9, 5, 116, 8, 9, -66, 443, -3, 1, -6, 5, -7 };	
 
int i_best = 0, j_best = 0; // индексы
int s_best = 0; // сумма
 
for(int i = 0; i < size; i++)
{
	for(int j = i + 1; j < size; j++)
	{
		int s = 0;
		for (int k = i; k < = j; k++)
		{
			s += arr[k];
		}
		if(s_best < s)
		{
			i_best = i;
			j_best = j;
			s_best = s;
		}
	}
}

Ожидаемые вопросы

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

Оценка результатов:

Никаких особых знаний, которые отличают юниора от более опытных соискателей, для задачи не нужно. Существует решение с линейной сложностью без выделения дополнительной памяти – его и нужно найти.