MODULE MaxNiza;
FROM InOut IMPORT WriteString,ReadString,
           WriteInt,WriteCard,WriteLn;
FROM FIO IMPORT File, Open, Close, RdInt,EOF;
FROM Str IMPORT Length;

CONST
  MaxN = 100;
TYPE
  Interval = [1..MaxN];
VAR
  X : ARRAY Interval OF INTEGER;
  f: File;
  N:CARDINAL;
  ime : ARRAY [1..50] OF CHAR;
  
PROCEDURE MaxNiza3();
(* Trece resenje: O(n^2). 
   Koristi pomocni niz u kome je na i-tom mestu
   suma podniza x[1..i] *)
VAR
  Max, Suma : INTEGER;
  d,g,i,Ood,Doo : Interval;
  Pom : ARRAY [0..MaxN] OF INTEGER;
  brojOp : CARDINAL;
BEGIN
  brojOp := 0;
  Pom[0] := 0;
  Ood := 1;
  Doo := 1;
  FOR i := 1 TO N DO
    Pom[i] := Pom[i-1] + X[i];
    INC(brojOp);
  END;
  Max := 0;
  FOR d := 1 TO N DO
    FOR g := d TO N DO
      Suma := Pom[g] - Pom[d-1];
      INC(brojOp);
      IF Suma > Max THEN
        Max := Suma;
        Ood := d;
        Doo := g
      END
    END
  END;
  WriteLn;
  WriteString(' Maksimum je ');
  WriteInt(Max,3);
  WriteString(' u intervalu od ');
  WriteCard(Ood,3);
  WriteString(' do ');
  WriteCard(Doo,3);
  WriteLn;
  WriteString('Broj racunskih operacija: ');
  WriteCard(brojOp,1);
  WriteLn;
END MaxNiza3;
  
PROCEDURE MaxNiza4();
(* Cetvrto resenje. Najbolje moguce: O(n)  *)
VAR
  Max, MaxDovde : INTEGER;
  i,d,Ood,Doo : Interval;
  brojOp : CARDINAL;
BEGIN
  Ood := 1;
  Doo := 1;
  brojOp := 0;
  d := 1;
  Max := 0;
  MaxDovde := 0;
  FOR i := 1 TO N DO
    IF MaxDovde = 0 THEN
      d := i
    END;
    MaxDovde := MaxDovde + X[i];
    INC(brojOp);
    IF MaxDovde < 0 THEN
      MaxDovde := 0
    END;
    IF MaxDovde > Max THEN
      Ood := d;
      Doo := i;
      Max := MaxDovde
    END
  END;
  WriteLn;
  WriteString(' Maksimum je ');
  WriteInt(Max,3);
  WriteString(' u intervalu od ');
  WriteCard(Ood,3);
  WriteString(' do ');
  WriteCard(Doo,3);
  WriteLn;
  WriteString('Broj racunskih operacija: ');
  WriteCard(brojOp,1);
  WriteLn;
END MaxNiza4;
  
BEGIN
  WriteString('ime fajla?');
  ReadString(ime);
  IF Length(ime)= 0 THEN
    ime := 'br1.txt';
  END;
  WriteString(' Unos niza X ');
  WriteLn;
  f := Open(ime);
  N:=0;
  EOF:=FALSE;
  WHILE NOT EOF DO
    INC(N);
    X[N] := RdInt(f);
    WriteCard(N,1);
    WriteString(' - ');
    WriteInt(X[N],1);
    WriteLn;
  END;
  Close(f);
  WriteString("metod 3");
  MaxNiza3();
  WriteString("metod 4");
  MaxNiza4();
END MaxNiza.