ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти интервал, на котором сумма максимальная
22 сообщений из 22, страница 1 из 1
Найти интервал, на котором сумма максимальная
    #39524061
NightBomber
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NightBomber
Участник
Всем привет.

Помогите с азимутом поиска задачю. Даже не знаю, как соотв-щая область математики зовётся.
В общем есть временной интервал и для каждого момента времени - результат вычисления некоторой ф-ции:
time07:0007:0507:1007:1507:2007:2507:3007:3507:4007:4507:5007:55func-1917123-812-11-21311-101
Требуется найти такую часть этого интервала, на котором сумма результатов ф-ции будет максимальной.
Часть интервала может содержать от 1 до N элементов и может начинаться / заканчиваться на любом из них.

Как такое решать ? Неужели только тупым перебором ?
...
Рейтинг: 0 / 0
21.09.2017, 00:24
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524064
NightBomber
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NightBomber
Участник
Отбой, кажись. Нарыл, что это такое:

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

Буду теперь осиливать алгоритмы.
...
Рейтинг: 0 / 0
21.09.2017, 00:35
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524066
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
YuRock
Участник
NightBomberНеужели только тупым перебором ?Даже не представляю, как по-другому можно получить суммы всех интервалов, чтобы сравнить их.
В один проход делается ведь (в двух циклах).
...
Рейтинг: 0 / 0
21.09.2017, 01:04
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524069
NightBomber
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NightBomber
Участник
Наивный перебор - это O(n^3). А умные люди, оказывается, давно нашли алгоритмы со сложностью O(n).

http://e-maxx.ru/algo/maximum_average_segment
http://rosettacode.org/wiki/Greatest_subsequential_sum#Python
...
Рейтинг: 0 / 0
21.09.2017, 01:25
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524082
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
NightBomberВсем привет.

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

Как такое решать ? Неужели только тупым перебором ?Двигаясь с левого края, суммируем. Если сумма стала отрицательной, обнуляем ее, и левый край интервала сдвигаем на следующий элемент. Запоминаем, на каком интервале сумма достигла максимума. Вроде в один проход получается.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
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;
  }
}


Вот примерно так
...
Рейтинг: 0 / 0
21.09.2017, 07:08
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524085
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Сворачиваете массив данных, суммируя соседние данные одного знака. Исходный массив
time7:007:057:107:157:207:257:307:357:407:457:50func-1917123-812-11-21311-10
преобразуется в
time7:007:05-7:157:207:257:30-7:357:40-7:457:50func-1941-812-1324-10
Следующий этап свёртки такой: Если абс. значение отрицательного элемента меньше значения каждого из положительных соседей - эти три элемента сворачиваются в один (само собой, краевые отрицательные алгоритм игнорирует, у них нет одного из соседей). Массив преобразуется в
time7:007:05-7:257:30-7:357:40-7:457:50func-194511-10-10
Этот этап повторяется до тех пор, пока не кончатся группы, пригодные к свёртке.

Осталось выбрать максимальное положительное значение, в данном случае это интервал 7:05-7:25 и сумма 45.
...
Рейтинг: 0 / 0
21.09.2017, 07:38
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524087
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Пардон, ошибка от невнимательности. Вот правильный вариант:

Сворачиваете массив данных, суммируя соседние данные одного знака. Исходный массив
time7:007:057:107:157:207:257:307:357:407:457:50func-19 17 1 23 -812-11-2 13 11 -10
преобразуется в
time7:007:05-7:157:207:257:30-7:357:40-7:457:50func-1941-812-1324-10
Следующий этап свёртки такой: Если абс. значение отрицательного элемента меньше значения каждого из положительных соседей - эти три элемента сворачиваются в один (само собой, краевые отрицательные алгоритм игнорирует, у них нет одного из соседей). Этап повторяется, пока возможно.

На первом шаге массив
time7:007:05-7:157:207:257:30-7:357:40-7:457:50func-19 41 -8 12 -1324-10
преобразуется в
time7:007:05-7:257:30-7:357:40-7:457:50func-19 45 -13 24 -10
Возможен ещё один шаг этапа, он даёт
time7:007:05-7:457:50func-1956-10
Ответ: интервал 7:05-7:45, сумма 56.
...
Рейтинг: 0 / 0
21.09.2017, 07:47
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524166
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Почему сворачиваем?
Надо разворачивать.
В N раз.

Лет 20 назад вставала такая практическая задача.
Только диапазон был не дискретный.
Не помню как решали...
...
Рейтинг: 0 / 0
21.09.2017, 10:18
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524167
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
сории. понял задачу ствертки.
...
Рейтинг: 0 / 0
21.09.2017, 10:19
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524168
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
AkinaОсталось выбрать максимальное положительное значение, в данном случае это интервал 7:05-7:25 и сумма 45.
Но это при N>=3
А если N=2 ?
...
Рейтинг: 0 / 0
21.09.2017, 10:21
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524173
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
982183 , ты о чём? После первой свёртки положительные и отрицательные числа всегда чередуются. Ибо, как я понял из формулировки задачи, нужно найти именно подпоследовательность с максимальной суммой без ограничения по количеству элементов в ней.

Если же надо найти макс. подпоследовательность со строго заданным количеством элементов или не длиннее заданной, то я бы применил заливку прямоугольной матрицы из N строк, где M(i+1,j) = M(i,j) + M(0,j+1), с последующим поиском глобального максимума.
...
Рейтинг: 0 / 0
21.09.2017, 10:27
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524184
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Akina Ибо, как я понял из формулировки задачи, нужно найти именно подпоследовательность с максимальной суммой без ограничения по количеству элементов в ней.


NightBomber "Часть интервала может содержать от 1 до N элементов и может начинаться / заканчиваться на любом из них."
...
Рейтинг: 0 / 0
21.09.2017, 10:38
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524271
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
982183 , угу, в этом контексте можно воспринимать N двояко: или как некое заранее заданное значение, или как количество элементов исходного массива. Тебе нравится первый вариант, мне второй. Автор мог бы уточнить, но молчит аки партизан.
...
Рейтинг: 0 / 0
21.09.2017, 11:52
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524360
scf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
scf
Участник
Эту задачу любят давать на собеседованиях
...
Рейтинг: 0 / 0
21.09.2017, 14:18
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524411
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Akina,

Не согласен. Говорится о "части" интервала. а не о "интервале"
+ в твоей трактовке задача тривиальна.
А твоё решение отвечает на вопрос - "наибольший положительный интервал"

+А во входных данных может быть 1 1 1 1 99 -1 99 1 1 1 1
при N=3
...
Рейтинг: 0 / 0
21.09.2017, 15:36
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524413
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Хотя нет. Всё зависит от количества "шагов"
...
Рейтинг: 0 / 0
21.09.2017, 15:38
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524424
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
982183Не согласен. Говорится о "части" интервала. а не о "интервале"Весь интервал тоже является частью интервала.
Впрочем, какая в пень разница? пусть ТС нарисуется и уточнит постановку задачи, тогда будем дальше воздух трясти.
...
Рейтинг: 0 / 0
21.09.2017, 15:48
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524426
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
А как твой способ будет работать, если в массиве будут только положительные значения?
...
Рейтинг: 0 / 0
21.09.2017, 15:51
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524443
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
982183как твой способ будет работать, если в массиве будут только положительные значения?На первом этапе свёртки останется единственное значение. Оно и будет решением.
...
Рейтинг: 0 / 0
21.09.2017, 16:21
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524499
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
982183,

Это самый прямой пример доказательного программирования. :)

Логика следующая:
1. Если 2 положительных числа идут подряд, то их сумма всегда будет больше каждого из них, и потому если в интервал включено одно из чисел, то обязательно будет включено и рядом стоящее положительное
2. Если числа чередуются + - +, и отрицательное число меньше каждого из положительных, то сумма трёх чисел будет больше любого из них и если в интервал включено хоть одно, то обязательно будут включены все 3.

Но в этом решении есть один большой минус, оно даст неверный результат при следующих входных данных:
20 -10 5 -10 20

Эти интервалы сложены не будут, и максимум определится как 20. Хотя сложив все 5 чисел получим ответ 25 :) Так что алгоритм неполон, а соответственно неверен. Сворачивания недостаточно для определения правильного результата!
...
Рейтинг: 0 / 0
21.09.2017, 18:52
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524504
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
А верный алгоритм следующий:
1. n = 0
2. для каждого элемента массива в направлении слева-направо:
2.1 n += k, где k - значение выбранного элемента массива
2.2 Если n <= k, то n = k, а для указанного массива ставим пометку левого края интервала
3. n = 0
4. для каждого элемента массива в направлении справа-налево:
4.1 n += k, где k - значение выбранного элемента массива
4.2 Если n <= k, то n = k, а для указанного массива ставим пометку правого края интервала
6. находим все пары пометок левая-правая (обязательно в таком порядке, пара - имеется ввиду пометки, между которыми нет других... ближайшие) и считаем сумму между ними. Пара с максимальной суммой и будет искомым интервалом.
...
Рейтинг: 0 / 0
21.09.2017, 19:04
| Ответить | Цитировать | Написать  
Найти интервал, на котором сумма максимальная
    #39524511
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
я тут оговорочку одну допустил:
а для указанного массива элемента массива ставим пометку...
...
Рейтинг: 0 / 0
21.09.2017, 19:33
| Ответить | Цитировать | Написать  
22 сообщений из 22, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти интервал, на котором сумма максимальная
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]