Что общего у собеседования кодера и игры «Змейка»?

[frostspb]

Nokia 5110 :)

[pushal]

скорее Nokia 3210 =)

[Rochfort]

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

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

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

Или я что-то упускаю?

[khim]

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

[Rochfort]

Почем вы решили, что вернётся неправильная сумма?

Потому что я запустил приведенный код и проверил что результат неверный. Условие выхода из цикла сработает в тот момент, когда подпоследовательность заполнится. Но это не значит что функция обработает всю последовательность. Остальные элементы даже не будут рассматриваться.

[Rochfort]

Кажется я понял, что я ошибся. Параметр n в функции max_sum_subsequence не максимальная длинна подпоследовательности, а длинна самой последовательности.
Извините за панику.

[khim]

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

[DrLivesey]

Длина массива, как известно, в C/C++ в функцию не передаётся

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

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

[Sirion]

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

[PatientZero]

Спасибо на добром слове.

[Limon2me]

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

Подскажите пожалуйста, как найти этот список? Или может перечислите их, чтобы самому изучить.) Спасибо.

[nobodyhave]

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

[zharko_mi]

Это работать не будет:
sum = sum — data[i — k] + data[i];

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

[FadeToBlack]

Или можно применить алгоритм Кэхэна

[humbug]

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

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

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

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

curSum [2] = 4
curSum [2, 3] = 7
curSum [2, 3, 1] = 8