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

[febb]

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

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

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

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

Comments

[bespechnoepero.livejournal.com]

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

[febb.livejournal.com]

Алгоритм очень просто - 15 строчек :)
И сложность O(n).