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

← →
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 ©

Неправильно

← →
Igorek © (2004-06-23 16:49) [29]

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

← →
Sandman25 © (2004-06-23 16:50) [30]

[28] вразлет © (23.06.04 16:47)

Контрпример можно?

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

panov ©

Что делать будем? Вон Панов уже сдался(

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

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

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

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

← →
nikkie © (2004-06-23 16:51) [33]

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

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

Sandman25 ©

Ты ищешь последовательность увеличивающихся символов

← →
nikkie © (2004-06-23 16:54) [35]

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

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

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

← →
Sandman25 © (2004-06-23 16:56) [37]

[32] vecna © (23.06.04 16:51)

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

← →
Sandman25 © (2004-06-23 16:59) [38]

[34] вразлет © (23.06.04 16:52)

Нет. Пример массива приведите, пожалуйста

← →
Fredericco © (2004-06-23 17:01) [39]

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

← →
Sandman25 © (2004-06-23 17:03) [40]

[39] Fredericco © (23.06.04 17:01)

см. [38] :)

← →
вразлет © (2004-06-23 17:04) [41]

Sandman25 ©

1 2 1

← →
Sandman25 © (2004-06-23 17:05) [42]

[41] вразлет © (23.06.04 17:04)

4

← →
вразлет © (2004-06-23 17:08) [43]

1 2 1 -1 -1 3

← →
Fredericco © (2004-06-23 17:09) [44]

1 -2 2 1
Если правильно понял условие то должно быть 3 [..,..,2,1]
А у тебя получиться 4 [1,..,2,1].
Вроде как ряд суммы должен быть непрерывным...

← →
blackman © (2004-06-23 17:10) [45]

Но что же тогда они предлагают решить перед увольнением ?

← →
Sandman25 © (2004-06-23 17:11) [46]

[43] вразлет © (23.06.04 17:08)

5

← →
Romkin © (2004-06-23 17:11) [47]

Тесты, плиз:
[5, -12, 4, -2, 4, -3] = 6
[15, -12, 34, -27, 12, -23] = 37
[15, -12, 34, -27, 28, -23] = 38

← →
Sandman25 © (2004-06-23 17:11) [48]

[44] Fredericco © (23.06.04 17:09)

3

← →
panov © (2004-06-23 17:12) [49]

>Fredericco © (23.06.04 17:09) [44]

Как ни странно, но код Sandman25 работает правильно-)

← →
Sandman25 © (2004-06-23 17:13) [50]

[47] Romkin © (23.06.04 17:11)

6
37
38

В-общем, мой алгоритм правильный. Кто не согласен, может проверить в Delphi самостоятельно. я устал :)

← →
вразлет © (2004-06-23 17:15) [51]

Sandman25 ©

Та находишь сумму, а не сам подмассив

← →
Рыба © (2004-06-23 17:17) [52]

15 минут.

function GetMaxPath(const A: array of Integer): TPoint;
var i, MaxS, S: Integer;
MaxSP, P: TPoint;
Sbros: Boolean;
begin
S := A[0];
P := Point(0, 0);
MaxS := S;
MaxSP := P;
Sbros := False;
for i := 1 to High(A) do begin
if A[i] < 0 then begin
if MaxS < S then begin
MaxS := S;
MaxSP := P;
end;
if MaxS < A[i] then begin
MaxS := A[i];
MaxSP := Point(i, i);
end;
Sbros := True;
end
else begin
if Sbros then begin
P := Point(i, i);
S := A[i];
Sbros := False;
end
else begin
Inc(S, A[i]);
Inc(P.y);
end;
end;
end;
if MaxS < S then Result := P
else Result := MaxSP;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
Randomize;
end;

procedure TForm1.Button1Click(Sender: TObject);
const Length = 10;
var i: Integer;
begin
ListBox1.Clear;
SetLength(FMass, Length);
for i := 0 to Length - 1 do begin
FMass[i] := Random(20) - Random(15);
ListBox1.Items.Add(IntToStr(FMass[i]));
end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var P: TPoint;
i: Integer;
begin
ListBox2.Clear;
P := GetMaxPath(FMass);
for i := P.x to P.y do
ListBox2.Items.Add(IntToStr(FMass[i]));
end;

← →
YurikGL © (2004-06-23 17:17) [53]

Реализовал, вроде работает правильно.
Суть в том, что формируется матрица NxN сумм, т.е. в элементе матрицы [2,5] содержится сумма элементов от 2-го до 5-го. Матрица формируется в один проход. Потом просто ищется максимум.

Реализовал с треугольной матрицей.

← →
Romkin © (2004-06-23 17:18) [54]

Sandman25 © (23.06.04 17:13) [50] Код правильный :)))

← →
Sandman25 © (2004-06-23 17:20) [55]

[51] вразлет © (23.06.04 17:15)

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

Еще 3 минуты работы :)

← →
panov © (2004-06-23 17:23) [56]

>вразлет © (23.06.04 17:15) [51]

Алгоритм от Sandman25 тривиально изменяется для возврата границ получаемого подмассива:
function MaxSum(const A: array of Integer;var bIndex,eIndex: Integer): integer; var I: word; CurrentSum,Sum: Integer; begin Result := A[0]; CurrentSum := Result; bIndex := 0; eIndex := 0; for I := 1 to High(A) do begin Sum := CurrentSum + A[I]; if Sum>A[i] then begin CurrentSum := Sum; eIndex := i; end else begin CurrentSum := A[i]; bIndex :=i; eIndex := i; end; if CurrentSum > Result then Result := CurrentSum; end; end; procedure TForm1.Button3Click(Sender: TObject); var b,e: Integer; begin ShowMessage(IntToStr(MaxSum( [15, -12, 34, -27, 28, -23],b,e))+":("+IntToStr(b)+","+IntToStr(e)+")"); end;

← →
вразлет © (2004-06-23 17:25) [57]

panov ©

Да знаю я, что уж и придраться нельзя?)

← →
YurikGL © (2004-06-23 17:27) [58]

Понимаю, что оперировал с массивом размерностью 5, на всегда можно поменять на N
mas: array [1..5] of integer;
mas2: array [1..5,1..5] of integer;
i,j,k,vr,n,m,j2,i2:integer;

mas[1]:=1; mas[2]:=5; mas[3]:=-1; mas[4]:=3; mas[5]:=0; for i:=1 to 5 do for j:=1 to 5 do mas2[i,j]:=0; for i:=1 to 5 do for j:=i to 5 do for k:=i downto 1 do mas2[j,k]:=mas2[j,k]+mas[i]; m:=0; j2:=0; i2:=0; for i:=1 to 5 do for j:=1 to i do if m<mas2[i,j] then begin m:=mas2[i,j]; j2:=j; i2:=i; end; ShowMessage("Промежуток ["+IntToStr(i2)+","+intToStr(j2)+"] сумма="+IntToStr(m));

← →
vecna © (2004-06-23 17:28) [59]

вот:
http://www.sql.ru/forum/actualthread.aspx?bid=9&tid=93718&hl=%f2%e5%f1%f2%ee%e2%fb%e5+%e7%e0%e4%e0%f7%e8

← →
vecna © (2004-06-23 17:35) [60]

panov ©
посмотрел ваш код, я придумал такой же... =)

Sandman25 ©
тоже посмотрел внимательно, соглашусь на то что правильно =))

← →
panov © (2004-06-23 17:41) [61]

>vecna © (23.06.04 17:35) [60]
это не мой, это Sandman25(c) -)

← →
Fredericco © (2004-06-23 17:42) [62]

2 Sandman25 ©
Согласен. Был не прав.

← →
default © (2004-06-23 18:09) [63]

такое не катит?
function SpecSum(Mas: Array of Integer): Integer;
var
i, j: Cardinal;
Sum: Integer;
begin
Result := Mas[0];
for i := 0 to High(Mas) do begin
Sum := Mas[i];
for j := i+1 to High(Mas) do begin
Inc(Sum, Mas[j]);
if Result < Sum then Result := Sum
end;
end;
end;

← →
Romkin © (2004-06-23 18:17) [64]

Такое не катит. Время О(n^2) :))

← →
Рыба © (2004-06-23 18:17) [65]

А мой код неверен.

← →
Romkin © (2004-06-23 18:53) [66]

А теперь финт ушами: Дан массив NxN целых чисел, найти в нем прямоугольную область с максимальной суммой. С наименьшей асимптотикой

А я бы как всегда рекурсивно решал. Люблю я рекурсию, и все тут!;) У меня все рекурсивно решается...

Хотя, придумал самый извращенный метод. Думаю, гигабайт 200 будет весить (помните про функцию перевертывания строки объемом в 450Гб?). Будет время, напишу;)

Люди, а меня в школе учили, что линейный алгоритм не может в себе иметь никаких циклов for т.д., а вас?

если
a11 a12 a13
a21 a22 a23
a31 a32 a33

a11a13, a11a13a21a23 прямоуг-ики?

Изврат писал-писал, запутался... Вообщем, написал простой пример. Где-то минут 10 потратил... Правда, наверное, это не совсем линейный алгоритм.
function MaxSumPos(const iArr: array of integer): tpoint; var // iMatrix: array of array of integer; i, j: integer; s, m: integer; begin m:=0; // SetLength(iMatrix, high(iArr)+1); for i:=0 to high(iArr) do begin s:=0; // SetLength(iMatrix[i], high(iArr)+1); for j:=i to high(iArr) do begin inc(s, iArr[j]); if s>m then begin m:=s; result.x:=i; result.y:=j; end; // iMatrix[i, j]:=s; // iMatrix[j, i]:=s; end; end; end; var a: array[0..4] of integer = (10, -10, 8, 3, -10); procedure SolveProblem; var r: tpoint; o: array of integer; i: integer; begin r:=MaxSumPos(a); SetLength(o, r.y-r.x+1); for i:=0 to high(o) do o[i]:=a[i+r.x]; //o - output end;

при собеседовании дали задачку
123 = 1
1234 = 1
12345 = 1
123456 = 1
1234567 = 1

расставте правильно знаки и скобки!

> [56] panov © (23.06.04 17:23)

Что-то мне не нравится этот код, впрочем так-же как и тот с которого его переделали. Думаю он в некоторых случаях все же будет выдавать неверные результаты... Например если в массиве все числа отрицательные...

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

Кстати выходной подмассив может быть пустым? или все же там должно быть не менее одного элемента?

[74] SergP © (24.06.04 08:54)

Вот более понятная запись:
if CurrentSum > 0 then
Inc(CurrentSum, A[I])
else
CurrentSum := A[I]

Паниковский[73]>
(1+2)/3 = 1
1*2+3-4 = 1
1-2+3+4-5 = 1
(1+2*3+4-5)/6 = 1
1*2+3+4+5-6-7 = 1

Bless
я не много не так делал
сказали не правильно((
1*(-2+3) = 1
(-1+2)*(-3+4) = 1
1*(-2+3)*(-4+5) = 1
(-1+2)*(-3+4)*(-5+6) = 1
1*(-2+3)*(-4+5)*(-6+7) = 1

Кстати задача надо правильно расставить операции скобки
как правильно?

123 = 1
1234 = 1
12345 = 1
123456 = 1
1234567 = 1

Sandman25[78]>
И то правда. Ты б то собеседование точно прошел, наверное :)
Сам догадался о таком решении?

Рискну, Алгоритм Карпа-Рабина?

> [76] Sandman25 © (24.06.04 09:12)
> [74] SergP © (24.06.04 08:54)
>
> Вот более понятная запись:
> if CurrentSum > 0 then
> Inc(CurrentSum, A[I])
> else
> CurrentSum := A[I]

предположем что массив такой:

[-4,-3,-4,-5]

что выдаст прога?

-3, конечно.

CurrentSum будет последовательно принимать значения каждого элемента

Только что зашел в ветку, решение получилось как у Sandman25. Динамика, однако :))

VEG © (23.06.04 19:40) [70]
> Люди, а меня в школе учили, что линейный алгоритм не может в себе иметь никаких циклов for т.д., а вас?

Ужас, это где такие школы (а может не школы? :). Никаких циклов, длина которых зависит от размера входа не может иметь алгоритм сложности O(1), а линейный алгоритм это как раз имеющий конечное число (читай не зависящее от входа) невложенных циклов, длина которых линейно зависит от размера входа.

[lamer]Barmaglot © (24.06.04 09:43) [83]
> Рискну, Алгоритм Карпа-Рабина?

Алгоритм Рабина-Карпа - это алгоритм поиска вхождений подстроки в строке. Работает, кстати, за O((n - m + 1) * m), n - длина строки, m - длина подстроки.

А мне вообще недавно на тестировании при приеме на работу дали задание решить 4 интеграла и найти четыре производных !

> infom ©
>
> Всего -то? Ты наверно на уборщика устраивался? Или на сторожа?

А нафига сторожам и уборщикам интегралы и производные?

[1,2,3,4,-1,2,3,4,-2,2,4,5]

что показываю ваши программы.?.:)

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