85 lines
1.6 KiB
Text
85 lines
1.6 KiB
Text
MODULE GreatestSubsequentialSum;
|
|
IMPORT
|
|
Out,
|
|
Err,
|
|
IntStr,
|
|
ProgramArgs,
|
|
TextRider;
|
|
TYPE
|
|
IntSeq= POINTER TO ARRAY OF LONGINT;
|
|
|
|
PROCEDURE ShowUsage();
|
|
BEGIN
|
|
Out.String("Usage: GreatestSubsequentialSum {int}+");Out.Ln
|
|
END ShowUsage;
|
|
|
|
PROCEDURE Gss(iseq: IntSeq; VAR start, end, maxsum: LONGINT);
|
|
VAR
|
|
i, j, sum: LONGINT;
|
|
BEGIN
|
|
i := 0; maxsum := 0; start := 0; end := -1;
|
|
WHILE (i < LEN(iseq^)) DO
|
|
sum := 0; j := i;
|
|
WHILE (j < LEN(iseq^) - 1) DO
|
|
INC(sum,iseq[j]);
|
|
IF sum > maxsum THEN
|
|
maxsum := sum;
|
|
start := i;
|
|
end := j
|
|
END;
|
|
INC(j)
|
|
END;
|
|
INC(i)
|
|
END
|
|
END Gss;
|
|
|
|
|
|
PROCEDURE GetParams():IntSeq;
|
|
VAR
|
|
reader: TextRider.Reader;
|
|
iseq: IntSeq;
|
|
param: ARRAY 32 OF CHAR;
|
|
argc,i: LONGINT;
|
|
res: SHORTINT;
|
|
BEGIN
|
|
iseq := NIL;
|
|
reader := TextRider.ConnectReader(ProgramArgs.args);
|
|
IF reader # NIL THEN
|
|
argc := ProgramArgs.args.ArgNumber();
|
|
IF argc < 1 THEN
|
|
Err.String("There is no enough arguments.");Err.Ln;
|
|
ShowUsage;
|
|
HALT(0)
|
|
END;
|
|
|
|
reader.ReadLn; (* Skips program name *)
|
|
|
|
NEW(iseq,argc);
|
|
FOR i := 0 TO argc - 1 DO
|
|
reader.ReadLine(param);
|
|
IntStr.StrToInt(param,iseq[i],res);
|
|
END
|
|
END;
|
|
RETURN iseq
|
|
END GetParams;
|
|
|
|
PROCEDURE Do;
|
|
VAR
|
|
iseq: IntSeq;
|
|
start, end, sum, i: LONGINT;
|
|
BEGIN
|
|
iseq := GetParams();
|
|
Gss(iseq, start, end, sum);
|
|
i := start;
|
|
Out.String("[");
|
|
WHILE (i <= end) DO
|
|
Out.LongInt(iseq[i],0);
|
|
IF (i < end) THEN Out.Char(',') END;
|
|
INC(i)
|
|
END;
|
|
Out.String("]: ");Out.LongInt(sum,0);Out.Ln
|
|
END Do;
|
|
|
|
BEGIN
|
|
Do
|
|
END GreatestSubsequentialSum.
|