Не пятница, но тем не менее...

← →
vecna © (2004-06-23 16:26) [0]

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

Надо найти в массиве размерностью N элеметов подмассив (непрерывный участок массива) с максимальной суммой. Количество элементов подмассива заранее неизвестно. Решение должно быть линейным (т.е. за один проход).

те кто уже знает, просьба не кидать ответ сразу. =)
предпологается, что есть 15-20 минут.

← →
Sandman25 © (2004-06-23 16:28) [1]

Решением будет весь исходный массив... или я что-то не понимаю

← →
vecna © (2004-06-23 16:30) [2]

нет естественно

[10, -10, 8, 3, -10]

ответ [8, 3]

← →
Nikolay M. © (2004-06-23 16:31) [3]

Может, есть массив некоей размерности и в нем нужно найти N элементов подряд? А то задача особого смысла не имеет, имхо.

← →
вразлет © (2004-06-23 16:32) [4]

vecna ©

А что за форум?))

← →
vecna © (2004-06-23 16:32) [5]

еще один пример:

[-10, -3, -2, -9]

ответ [-2]

← →
Ega23 © (2004-06-23 16:32) [6]

Фигня какая-то...

← →
Ega23 © (2004-06-23 16:33) [7]

ИМХО, такие задачки надо не на приёме на работу задавать, а на экзамене по информатике на первом курсе.

← →
Nikolay M. © (2004-06-23 16:34) [8]

> vecna © (23.06.04 16:30) [2]

Ах, вот так вот... Интересно :)

← →
panov © (2004-06-23 16:34) [9]

хм... вродк бы и решать-то нечего...

← →
vecna © (2004-06-23 16:34) [10]

вразлет,
потом скажу =), если сами не найдете

Nikolay M,
посмотрите на примеры... элементы подряд, но N не известно (читайте внимательно условие)

← →
panov © (2004-06-23 16:35) [11]

Сейчас для интереса засеку время, сколько понадобится для полной реализации алгоритма-)

← →
vecna © (2004-06-23 16:37) [12]

Ega23 © (23.06.04 16:32) [6]
Фигня какая-то...

полностью согласен, но все же...

← →
Prosvet © (2004-06-23 16:38) [13]

>[10, -10, 8, 3, -10]

>ответ [8, 3]

А почему не [10, -10, 8, 3]. Сумма ведь та же.

← →
вразлет © (2004-06-23 16:39) [14]

и тут час нет Панова, два часа нет Панова, три часа нет Панова...

← →
Layner © (2004-06-23 16:40) [15]

На SQL.RU и искал бы ответа, там эта тема несколько страниц занимала.

← →
Romkin © (2004-06-23 16:41) [16]

vecna © (23.06.04 16:32) [5] Неверно, в оригинале 0 - сумма только положительная.
"Жемчужины программирования" - это оттуда. И в ответе должна быть только сумма. Никто не спрашивает границы элементов ;)
Иначе О(n) фиг получится ;)

← →
vecna © (2004-06-23 16:41) [17]

Prosvet © согласен... плохой пример,
но идея ясна =)

← →
YurikGL © (2004-06-23 16:42) [18]

> vecna © (23.06.04 16:26)

Минут семь алгоритм придумывал.

← →
YurikGL © (2004-06-23 16:43) [19]

> Romkin © (23.06.04 16:41) [16]

Кто мешает в конце делать проверку, если <0 то сумма=0

← →
vecna © (2004-06-23 16:43) [20]

Romkin © как там написано, так и я написал.... имхо, найти сумму или гранцы, никак не влияет на сложность.

← →
Romkin © (2004-06-23 16:43) [21]

Кстати, [-12, 34, -6, 5, 8, -45, 10] результат 41 должен быть ;)
(34 - 6 + 5 + 8)

← →
Romkin © (2004-06-23 16:44) [22]

vecna © (23.06.04 16:43) [20] Еще как влияет!!!

← →
vecna © (2004-06-23 16:44) [23]

"в оригинале 0 - сумма только положительная."

такого условия нет, задача сформулирована четко.

← →
panov © (2004-06-23 16:45) [24]

Не, не дают на работе заняться.-(

Но алгоритм ведь простой...

← →
Sandman25 © (2004-06-23 16:45) [25]

За 6 минут написал. Правильно?

function MaxSum(const A: array of Integer): Integer;
function Max(A1, A2: Integer): Integer;
begin
if A1 > A2 then
Result := A1
else
Result := A2
end;
var
I: word;
CurrentSum: Integer;
begin
Result := A[0];
CurrentSum := Result;
for I := 1 to High(A) do
begin
CurrentSum := Max(CurrentSum + A[I], A[I]);
if CurrentSum > Result then
Result := CurrentSum;
end;
end;

← →
Prosvet © (2004-06-23 16:46) [26]

>Prosvet © согласен... плохой пример,
>но идея ясна =)

В том то и дело, что не ясна. Эта последовательность должна содержать минимальное количество элементов или какое попало?

← →
vecna © (2004-06-23 16:47) [27]

YurikGL ©
предлагайте алгоритм, код не нужен, я верю что все в состоянии =)

Romkin ©
нет, по крайней мере в моих решениях, две лишних переменных для хранения интервала только добавятся.

← →
вразлет © (2004-06-23 16:47) [28]

Sandman25 ©

Неправильно

имхо нетривиальный алгоритм нужен; вроде было такое в "Жемчужинах программирования";

Prosvet ©
>В том то и дело, что не ясна. Эта последовательность должна >содержать минимальное количество элементов или какое попало?

максимальная сумма... интервал любой, если максимумов несолько

Sandman25 ©
на первый взгляд не правильно, но утверждать не стану, проверить не могу нет компилятора, а код разбирать лень, расскажите идею..

перебираем i от 1 до N
храним 2 диапазона вида [a,b], где b<>i, и [c,i] с с максимальными суммами в своем классе.
по идее, легко написать пересчет этих интервалов при увеличении i на 1.

> 2 диапазона вида [a,b], где b<>i, и [c,i] с с максимальными суммами в своем классе.
уточню: a<=b<i, c<=i.

понятно... =)))
пойду я покурю пока... уже 30 минут прошло...
еще 30 минут, и я опубликую ссылку где я это накопал

[32] vecna © (23.06.04 16:51)

Математическая индукция. Сначала текущая сумма = первый элемент.
Следующая текущая сумма либо равна следующему элементу, либо текущей сумме + следующий элемент...
М-да, кодом понятнее ИМХО. Все примеры из этой ветки дали правильный результат.
Для получения массива надо еще накапливать используемые элементы - как реализовать ясно - добавляются аргументы к Max, но неохота возиться :)

2 Sandman25 © (23.06.04 16:56) [37]
Согласен с вразлет © (23.06.04 16:52) [34] ,
ты прибавляешь любой элемент который больше суммых таких же предыдущих.

Не пятница, но тем не менее... Найти похожие ветки