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

Опубликовано 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. Задача очевидно имеет неоднозначное решение по аналогии с алгоритмом поиска максимума в массиве. Какие индексы нужно вернуть, если решений имеется больше одного?

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

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


8 Коммент. : “Подмассив с максимальной суммой элементов”

  1. Антон says:

    Очевидно, что задача решается рекурсивным делением массива на два и поиском максимальных цепочек в левой, правой частях, а также при пересечении середины. Более подробно опишу позже, смутил только тезис о линейности алгоритма… Для уточнения – имеется в виду O(n)?

    Тогда мое решение не подходит, но в этом случае хотелось бы увидеть это самое решение O(n) :)

    • Возможно тот факт, что сегодня пятница и конец рабочей недели, затрудняет ход мыслей, но представить способ решения, в котором фигурируют термины “деление массива” и “рекурсия” мне так и не удалось :)

      • Антон says:

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

        • Спасибо, обязательно посмотрю книжку с таким автором (ранее не читал).

          В силу специфики задачи, а именно поиск НЕПРЕРЫВНОГО фрагмента массива с максимальной суммой элементов, мне показалось сложным найти смысл в алгоритме с его ДЕЛЕНИЕМ :) )

          Хотя, попробую пофантазировать – наверное, можно оправдать “деление массива” при попытке создания максимально эффективного алгоритма с использованием многопроцессорной/многоядерной архитектуры :) В таком случае можно параллельно сканировать “N” участков массива (по количеству свободных ядер в процессорах) и далее работать с локальными максимумами.

  2. Галина says:

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

    const int size = 15; 
    int arr[size] = {1110,2,6,-9,5,116,8,9,-66,443, -3, 1,-6,5,-7};	
     
    int begin = 0, end = 0, s_best = 0;
     
    int i = 0, j = 0; 
    int s = 0; 
    for(j = 0; j < size; j++)
    {
      if(arr[j] < 0) 
      {
        if(s_best < s) 
    	{ 
    		begin = i; 
    		end = j - 1; 
    		s_best = s; 
    	}
        s += arr[j];
        if(s <= 0) 
    	{ 
    		i = j + 1; 
    		s = 0; 
    	} 
      }
      else 
        s += arr[j];
    }
    if(s_best < s) 
    { 
    	begin = i; 
    	end = j - 1; 
    }

    Замечание. Результат – именно подмассив, который содержит больше, чем один элемент. То есть, begin и end должны отличаться друг от друга, и при этом, разумеется, begin < end.

    • Дмитрий Храмов says:

      Спасибо за задание. Я правда, из учебников смог припомнить только Бентли, а там линейное решение далось всем, кроме его автора, отнюдь не за полчаса:)
      Хорошо бы в качестве иллюстрации разместить картинку из того же Бентли, а то без подсказки я ухитрился решить другую задачу (потребовав непрерывности значений элементов, а не последовательности их индексов).

    • Вы пишите:
      “Замечание. Результат – именно подмассив, который содержит больше, чем один элемент. То есть, begin и end должны отличаться друг от друга, и при этом, разумеется, begin < end.”

      Почему считается, что ответом на задачу может быть только подмассив содержащий более 1 элемента?
      Например, в случае если исходный массив состоит из двух элементов, то по предположению выше ответ должен быть всегда [0, 1].

      Но если задать решению выше массив {5, -7}, то логично предположить, что ответ должен быть [0, 0]. Впрочем решение именно этот ответ и выдает.

      Получается, что либо решение неверное, либо замечание.

  3. Это пример решения задачи, но только без нахождения индексов.

    int lin_sum(int *a, int low, int high){
      int m_now=0;
      int m_far=0;
      for(int i=low;i<=high;i++){
        m_now=m_now+a[i];
        if(m_now<0)
          m_now=0;
        if(m_far<m_now)
          m_far=m_now;
      }
      return m_far;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*