Найти интервал, на котором сумма максимальная

Всем привет.

Помогите с азимутом поиска задачю. Даже не знаю, как соотв-щая область математики зовётся.
В общем есть временной интервал и для каждого момента времени - результат вычисления некоторой ф-ции:

time 07:00 07:05 07:10 07:15 07:20 07:25 07:30 07:35 07:40 07:45 07:50 07:55 func -19 17 1 23 -8 12 -11 -2 13 11 -10 1

Требуется найти такую часть этого интервала, на котором сумма результатов ф-ции будет максимальной.
Часть интервала может содержать от 1 до N элементов и может начинаться / заканчиваться на любом из них.

Как такое решать ? Неужели только тупым перебором ?

Отбой, кажись. Нарыл, что это такое:

https://en.wikipedia.org/wiki/Maximum_subarray_problem

Буду теперь осиливать алгоритмы.

NightBomber
Неужели только тупым перебором ?

Даже не представляю, как по-другому можно получить суммы всех интервалов, чтобы сравнить их.
В один проход делается ведь (в двух циклах).

Наивный перебор - это O(n^3). А умные люди, оказывается, давно нашли алгоритмы со сложностью O(n).

http://e-maxx.ru/algo/maximum_average_segment
http://rosettacode.org/wiki/Greatest_subsequential_sum#Python

NightBomber

Всем привет. Помогите с азимутом поиска задачю. Даже не знаю, как соотв-щая область математики зовётся. В общем есть временной интервал и для каждого момента времени - результат вычисления некоторой ф-ции: timet07:00t07:05t07:10t07:15t07:20t07:25t07:30t07:35t07:40t07:45t07:50t07:55 funct-19t17t1t23t-8t12t-11t-2t13t11t-10t1 Требуется найти такую часть этого интервала, на котором сумма результатов ф-ции будет максимальной. Часть интервала может содержать от 1 до N элементов и может начинаться / заканчиваться на любом из них. Как такое решать ? Неужели только тупым перебором ?

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

leftmax=0; rightmax=0; summax=0;
left=0; sum=0;
for(right=0; right<N; ++right)
{
  sum += arr[right];
  if (sum > summax) 
  {
     summax = sum;
     leftmax = left;
     rightmax = right;
  }
  if (sum < 0)
  {
     sum = 0;
     left = right+1;
  }
}

Вот примерно так

Сворачиваете массив данных, суммируя соседние данные одного знака. Исходный массив

time 7:00 7:05 7:10 7:15 7:20 7:25 7:30 7:35 7:40 7:45 7:50 func -19 17 1 23 -8 12 -11 -2 13 11 -10

преобразуется в

time 7:00 7:05-7:15 7:20 7:25 7:30-7:35 7:40-7:45 7:50 func -19 41 -8 12 -13 24 -10

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

time 7:00 7:05-7:25 7:30-7:35 7:40-7:45 7:50 func -19 45 11 -10 -10

Этот этап повторяется до тех пор, пока не кончатся группы, пригодные к свёртке.

Осталось выбрать максимальное положительное значение, в данном случае это интервал 7:05-7:25 и сумма 45.

Пардон, ошибка от невнимательности. Вот правильный вариант:

Сворачиваете массив данных, суммируя соседние данные одного знака. Исходный массив

time 7:00 7:05 7:10 7:15 7:20 7:25 7:30 7:35 7:40 7:45 7:50 func -19 17 1 23 -8 12 -11 -2 13 11 -10

преобразуется в

time 7:00 7:05-7:15 7:20 7:25 7:30-7:35 7:40-7:45 7:50 func -19 41 -8 12 -13 24 -10

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

На первом шаге массив

time 7:00 7:05-7:15 7:20 7:25 7:30-7:35 7:40-7:45 7:50 func -19 41 -8 12 -13 24 -10

преобразуется в

time 7:00 7:05-7:25 7:30-7:35 7:40-7:45 7:50 func -19 45 -13 24 -10

Возможен ещё один шаг этапа, он даёт

time 7:00 7:05-7:45 7:50 func -19 56 -10

Ответ: интервал 7:05-7:45, сумма 56.

Почему сворачиваем?
Надо разворачивать.
В N раз.

Лет 20 назад вставала такая практическая задача.
Только диапазон был не дискретный.
Не помню как решали...

сории. понял задачу ствертки.

Akina
Осталось выбрать максимальное положительное значение, в данном случае это интервал 7:05-7:25 и сумма 45.

Но это при N>=3
А если N=2 ?