Pull to refresh

Comments 15

Не могу понять один момент в задаче 2:

создать алгоритм нахождения подпоследовательности с наибольшей суммой из всех возможных подпоследовательностей

Если в представленной на рисунке 7 последовательности изменить последний элемент с 1 на 200, то функция max_sum_subsequence все равно вернет подпоследовательность [3 9 -2 -4 0 2 6] как с наибольшей суммой из всех возможных, хотя очевидно, что наибольшая сумма будет у подпоследовательности из 3-х последних элементов [2 3 200].

Или я что-то упускаю?
Сложно сказать что вы упускаете если вы не ничего не поясняете. Почем вы решили, что вернётся неправильная сумма?
Почем вы решили, что вернётся неправильная сумма?

Потому что я запустил приведенный код и проверил что результат неверный. Условие выхода из цикла сработает в тот момент, когда подпоследовательность заполнится. Но это не значит что функция обработает всю последовательность. Остальные элементы даже не будут рассматриваться.
Кажется я понял, что я ошибся. Параметр n в функции max_sum_subsequence не максимальная длинна подпоследовательности, а длинна самой последовательности.
Извините за панику.
Вот теперь вы, я надеюсь, видите, почему вам никто не мог помочь. Представить себе, что n может быть чем-то иным, кроме как длиной последовательности я, например, не мог… Длина массива, как известно, в C/C++ в функцию не передаётся, а если вы её туда передали отдельно, то, вроде как, больше аргументов-то и нету…
Длина массива, как известно, в C/C++ в функцию не передаётся

Именно поэтому в С++ для динамических массивов надежнее пользоваться std::vector<T> а для статических std::array<T, N> (начиная с С++11).


Ну и конечно же не нужно в ручную заботиться о выделении/освобождении памяти.

Я сначала подумал, что будет очередной буллшит из серии «программирование по методу Кличко». Потом увидел автора и понял, что таки нет. Всё-таки ваш ник — это уже своеобразный знак качества. Вы выбираете интересные статьи и хорошо их переводите. Спасибо.
Несмотря на сложности алгоритмического программирования, существует достаточно короткий список принципов, необходимых для решения задач.

Подскажите пожалуйста, как найти этот список? Или может перечислите их, чтобы самому изучить.) Спасибо.
Это перевод. В оригинале списка нет. Ну и на самом деле список можно сделать весьма длинным, так решение многих задач состоит в использовании правильной структуры данных. А чтобы выбрать правильную, нужно знать их все. Иногда бывает решаешь задачку на соревновании, вроде и понимаешь, что надо сделать, а по времени не заходит. Потом внезапно оказывается, что какое-нибудь link cut tree эту задачу прекрасно решает.
Если говорить именно о техниках, то я бы назвал:
— sorting (во многих случаях сильно упрощает проблему, хотя далеко не всегда оптимально)
— two pointers
— sliding window
— square root decomposition в частности и использование buckets в целом
— divide and conquer
— greedy approach
— dynamic programming
— приведение задачи к графу и попытки решить через алгоритмы для графов
— ну и наконец перебор разных структур данных, авось какая подойдет
Это работать не будет:
sum = sum — data[i — k] + data[i];

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

У вас неправильное графическое представление 2 задачи на рисунке.


По словесному описанию и по алгоритму, реализованному на С++, мы сбрасываем последовательность только текущая сумма становится < 0.


Смотрим на графическое решение:


curSum = 14
... 
...   sum([-3, -5, 0, -4]) = -12, curSum = 2 // почему-то происходит сброс подпоследовательности и дальше считается отдельно:

curSum [2] = 4
curSum [2, 3] = 7
curSum [2, 3, 1] = 8
Only those users with full accounts are able to leave comments. Log in, please.

Articles