Отправлено: 15.01.21 09:21. Заголовок: 18. Задачи на последовательность.

День добрый!
Задачи на последовательность вещественных чисел. Возник вопрос:
Если по условию задачи в файле только положительные числа, проблем нет - стандартный алгоритм нахождения максимальной (минимальной) суммы подпоследовательности.
Если по условию задачи в файле как положительные так и отрицательные числа - обработка таких последовательностей для нахождения, например, максимальной суммы становится проблемой.
Например, интересует подпоследовательность, в которой разница между соседними элементами не менее 10. Найти максимальную сумму.
1) 10 20 30 40 - проблем нет, стандартный алгоритм работает,
2) -10 -20 -30 - 40 - проблем нет, стандартный алгоритм,
3) -100 -50 10 20 30 -10 -20 10 40 - 10 - 20 - в таких последовательностях возникает проблема - вначале последовательности идут отрицательные числа. Максимально возможная сумма - 80 (10 20 30 -10 -20 10 40). НО, отрицательные числа, стоящие в начале последовательности, не позволят нам получить этот результат. значит нам надо сохранять всю найденную последовательность и потом ее обрабатывать отдельно, а это уже совсем другая сложность задачи.

 Отправлено: 15.01.21 09:26. Заголовок: 4) -40 - 30 -20 -10 ..

4) -40 - 30 -20 -10 - такая же проблема как и в 3) - максимальная сумма -30, но начало последовательности даст нам другой результат - 100

 Отправлено: 15.01.21 11:23. Заголовок: https://i.ibb.co/tsn..

 Отправлено: 21.01.21 09:28. Заголовок: Последовательность, ..

Последовательность, в которой не работает:
-20
-40
-10
-20
-10
-20

Результат -10, но максимальная сумма нескольких элементов (2 и более) -30

Вторая последовательность:
-10
10
-10
10
-10
10
-10
Результат 10, а должен быть 0.

 Отправлено: 21.01.21 23:51. Заголовок: alspay пишет: максим..

alspay пишет:

цитата:

максимальная сумма нескольких элементов (2 и более)

Нигде не написано про 2 и более.

 Отправлено: 22.01.21 06:17. Заголовок: Поляков пишет: Нигд..

Поляков пишет:

цитата:

Нигде не написано про 2 и более.

Сумма может состоять из одного элемента?

 Отправлено: 22.01.21 09:35. Заголовок: alspay пишет: Сумма ..

alspay пишет:

цитата:

Сумма может состоять из одного элемента?

Да, конечно.

 Отправлено: 21.01.21 09:39. Заголовок: Константин Юрьевич, ..

Константин Юрьевич, возвращаясь к сложности заданий на последовательности.
В 18 задании в Вашей подборке встречаются не только последовательности на соседние элементы, но и задания в которых надо проанализировать элементы последовательности, номера которых отличаются не более (не менее) чем на К элементов, т.е. это бывшие 27 задания. Алгоритмы на этот тип задач не вызывают особых вопросов, но ведь 27 относится к высокому уровню сложности, а 18 задание это повышенный уровень.

 Отправлено: 21.01.21 23:52. Заголовок: alspay пишет: Алгори..

alspay пишет:

цитата:

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

Как говорил Суворов, "Тяжело в учении, ...".

 Отправлено: 25.01.21 08:15. Заголовок: alspay пишет: цитат..

цитата:

alspay пишет: цитата: Сумма может состоять из одного элемента? Да, конечно.

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

 Отправлено: 25.01.21 09:24. Заголовок: alspay пишет: значит..

alspay пишет:

цитата:

значит и сумма должна состоять из минимум 2 элементов.

Такого нет в условии. По умолчанию всегда предполагается, что последовательность может состоять из 1+ элементов. По крайней мере, в этой задаче условие именно такое. Можно решать и какие-то другие задачи, но тогда нужно особо оговаривать, что длина последовательности не менее X. В этом случае решение будет сложнее.

 Отправлено: 29.01.21 22:10. Заголовок: 3165,3194

Касательно задачи 3165
Немного не понимаю почему в ответе 3165 = 104 . Могу только предположить, что она получается как максимальное из столбца B. если пользоваться формулой , приведенной выше для столбца B =ЕСЛИ(И(ABS(A2-A1)<20;A2+B1>A2);B1+A2;A2).Как раз там и будет в ячейке B704 =104.38. Я не знаю каким способом решал автор задачи, НО даже , если пользоваться предложенной выше формулой получается казус , во-первых 104,38-это промежуточная сумма в последовательности, во-вторых - последовательности, применяя эту формулу, получается неверные(красным выделены числа, не включенные в последовательность, хотя они должны быть там).

По итогу, я полагаю, ответ должен быть 91. Пользовалась формулой =ЕСЛИ(ABS(A2-A1)<20;B1+A2;A2) и максимальное искала не в столбце B, тк промежуточные суммы в последовательностях могут быть больше итоговой суммы последовательности, а отдельно делала вывод итоговой суммы каждой последовательности и там уже...,.
Касательно задачи 3194 проблема та же - ответ 33 , хотя , я думаю, дб 31 - полагаю, что 33 это промежуточная сумма последовательности

Возможно, я в корне не права в своих рассуждениях.
Прошу дать объяснение , что не так .
Спасибо,за то что прочитали мой опус

 Отправлено: 29.01.21 23:10. Заголовок: Светлана111 пишет:во..

Светлана111 пишет:

цитата:

во-первых 104,38-это промежуточная сумма в последовательности

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

цитата:

красным выделены числа, не включенные в последовательность, хотя они должны быть там

Почему вы считаете, что они должны быть там?

 Отправлено: 30.01.21 10:48. Заголовок: Спасибо за ответ. По..

Спасибо за ответ. По поводу максимального разобралась- не поняла ТУ к задаче. Полагала, что нужно найти максимальное из финальных сумм существующих последовательностей, оказывается все гораздо проще...те. вопрос к 3194 снимается

НО вопрос по 3165 остался(почему ответ 104), все таки вот эти числа в " красном" должны быть в последовательности, тк разбег между ними меньше 20, соответственно и максимальную считает неверно, тк они не учтены.Это опять же , если использовать, предложенную Вами выше формулу.Кстати, я не совсем поняла, зачем там второе условие по И, которое как раз и дает вот такой результат.

 Отправлено: 30.01.21 16:50. Заголовок: Светлана111 пишет: ..

Светлана111 пишет:

цитата:

должны быть в последовательности, тк разбег между ними меньше 20

Мы вольны как включать, так и не включать их в последовательность. Если они увеличивают сумму, то включаем. Если не увеличивают - не включаем.

цитата:

зачем там второе условие по И

Как раз за этим. Чтобы найти максимальную возможную сумму.

 Отправлено: 30.01.21 20:12. Заголовок: Поляков пишет: Мы в..

Поляков пишет:

цитата:

Мы вольны как включать, так и не включать их в последовательность. Если они увеличивают сумму, то включаем. Если не увеличивают - не включаем.

Спасибо.
Я просто неверно изначально поняла суть задачи. Зачем-то усложнила условия, в первую очередь сделав упор на формирование последовательностей,, удовлетворяющих условию, а не на рассмотрение сумм, такая "сама себе Буратино".
Всю голову сломала, почему так.....
Еще раз спасибо.!