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

← →
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 целых чисел, найти в нем прямоугольную область с максимальной суммой. С наименьшей асимптотикой

← →
default © (2004-06-23 18:55) [67]

Romkin © (23.06.04 18:53) [66]
повезло слонам

← →
VEG © (2004-06-23 19:34) [68]

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

Хотя, придумал самый извращенный метод. Думаю, гигабайт 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

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