Просили подробно про интервью в Google...

[febb]

Гуглята издеваются на интервью. Например они задают такие классические задачки.

Дан массив целых чисел (положительные и отрицательные) найти кусок в этом массиве,
сумма элементов в котором максимальная.

Это известная задачка. Поэтому кто знает ответ, не залезая в Гугл,
может просто написать тут "знаю". Это своеобразные азы, ликбез
для молодого гугловода... :)

А кто не знает, можете предложить алгоритм тут.
Нам будет забавно узнать какие вы умные. :))

Comments

[andy-scott.livejournal.com]

построить дерево от листьев к вершине

листья - элементы массива

сумма 2 соседних элементов - узлы первого уровня (если нечетное к-во элементов, до дополняем до четного псевдоэлементом == 0)
сумма 4 соседних элементов - узлы 2 уровня
итд до корня

потом обойти дерево и найти узел/лист, в котором значение максимально

[andy-scott.livejournal.com]

ну и на всякий случай - первое дерево строим с array[0] второе точно так же но начиная с array[1]

и алгоритм выполняем дважды соответственно

[febb.livejournal.com]

И вообще нужно всё сделать в один проход :)

[andy-scott.livejournal.com]

Вообще да, я поторопился :)

и как же правильно решается задача?

[andy-scott.livejournal.com]

или однопроходный алгоритм с двумя ползущими указателями и "ощупыванием" вперед переднего на 1 элемент и назад от заднего на 1 элемент, запоминаем для макс. суммы значение и 2 индекса

[febb.livejournal.com]

Можно придумать массив, для котрого этот алгоритм бессилен.