Comments 15
Nokia 5110 :)
0
Не могу понять один момент в задаче 2:
создать алгоритм нахождения подпоследовательности с наибольшей суммой из всех возможных подпоследовательностей
Если в представленной на рисунке 7 последовательности изменить последний элемент с 1 на 200, то функция max_sum_subsequence все равно вернет подпоследовательность [3 9 -2 -4 0 2 6] как с наибольшей суммой из всех возможных, хотя очевидно, что наибольшая сумма будет у подпоследовательности из 3-х последних элементов [2 3 200].
Или я что-то упускаю?
создать алгоритм нахождения подпоследовательности с наибольшей суммой из всех возможных подпоследовательностей
Если в представленной на рисунке 7 последовательности изменить последний элемент с 1 на 200, то функция max_sum_subsequence все равно вернет подпоследовательность [3 9 -2 -4 0 2 6] как с наибольшей суммой из всех возможных, хотя очевидно, что наибольшая сумма будет у подпоследовательности из 3-х последних элементов [2 3 200].
Или я что-то упускаю?
0
Сложно сказать что вы упускаете если вы не ничего не поясняете. Почем вы решили, что вернётся неправильная сумма?
0
Почем вы решили, что вернётся неправильная сумма?
Потому что я запустил приведенный код и проверил что результат неверный. Условие выхода из цикла сработает в тот момент, когда подпоследовательность заполнится. Но это не значит что функция обработает всю последовательность. Остальные элементы даже не будут рассматриваться.
0
Кажется я понял, что я ошибся. Параметр n в функции max_sum_subsequence не максимальная длинна подпоследовательности, а длинна самой последовательности.
Извините за панику.
Извините за панику.
0
Вот теперь вы, я надеюсь, видите, почему вам никто не мог помочь. Представить себе, что
n
может быть чем-то иным, кроме как длиной последовательности я, например, не мог… Длина массива, как известно, в C/C++ в функцию не передаётся, а если вы её туда передали отдельно, то, вроде как, больше аргументов-то и нету…+1
Я сначала подумал, что будет очередной буллшит из серии «программирование по методу Кличко». Потом увидел автора и понял, что таки нет. Всё-таки ваш ник — это уже своеобразный знак качества. Вы выбираете интересные статьи и хорошо их переводите. Спасибо.
+4
Несмотря на сложности алгоритмического программирования, существует достаточно короткий список принципов, необходимых для решения задач.
Подскажите пожалуйста, как найти этот список? Или может перечислите их, чтобы самому изучить.) Спасибо.
+1
Это перевод. В оригинале списка нет. Ну и на самом деле список можно сделать весьма длинным, так решение многих задач состоит в использовании правильной структуры данных. А чтобы выбрать правильную, нужно знать их все. Иногда бывает решаешь задачку на соревновании, вроде и понимаешь, что надо сделать, а по времени не заходит. Потом внезапно оказывается, что какое-нибудь link cut tree эту задачу прекрасно решает.
Если говорить именно о техниках, то я бы назвал:
— sorting (во многих случаях сильно упрощает проблему, хотя далеко не всегда оптимально)
— two pointers
— sliding window
— square root decomposition в частности и использование buckets в целом
— divide and conquer
— greedy approach
— dynamic programming
— приведение задачи к графу и попытки решить через алгоритмы для графов
— ну и наконец перебор разных структур данных, авось какая подойдет
Если говорить именно о техниках, то я бы назвал:
— sorting (во многих случаях сильно упрощает проблему, хотя далеко не всегда оптимально)
— two pointers
— sliding window
— square root decomposition в частности и использование buckets в целом
— divide and conquer
— greedy approach
— dynamic programming
— приведение задачи к графу и попытки решить через алгоритмы для графов
— ну и наконец перебор разных структур данных, авось какая подойдет
+1
Это работать не будет:
В случае с плавающей запятой, будет ошибка накапливаться. Надо либо на инты перейти, либо для каждого значения отдельно сумму считать.
sum = sum — data[i — k] + data[i];
В случае с плавающей запятой, будет ошибка накапливаться. Надо либо на инты перейти, либо для каждого значения отдельно сумму считать.
+1
Или можно применить алгоритм Кэхэна
+1
У вас неправильное графическое представление 2 задачи на рисунке.
По словесному описанию и по алгоритму, реализованному на С++, мы сбрасываем последовательность только текущая сумма становится < 0.
Смотрим на графическое решение:
curSum = 14
...
... sum([-3, -5, 0, -4]) = -12, curSum = 2 // почему-то происходит сброс подпоследовательности и дальше считается отдельно:
curSum [2] = 4
curSum [2, 3] = 7
curSum [2, 3, 1] = 8
0
Sign up to leave a comment.
Что общего у собеседования кодера и игры «Змейка»?