{
Daná je postupnosť n celých čísel (kladných a záporných). Napíšte
algoritmus, ktorý nájde podpostupnosť (ľubovoľnej dĺžky <= n) po sebe
nasledujúcich členov postupnosti s najväčším súčtom. Aplikovať postup
zlepšovania riešenia.
}

program Project1;

const max = 7;
type TZoznam = record
          pole:array[1..max] of integer;
          pocet:integer;
     end;
     TVysledok = record
         zoznam:TZoznam;
         sucet:integer;
         zaciatok, koniec:integer;
     end;
     TTransf = record
         casti:array [1..max] of TZoznam;
         sucty:array[1..max] of integer;
         pocet:integer;
     end;

const zoznam :TZoznam =(pole:(-1, -3, 4, -3, 6, 3, -5); pocet:max);

var trend:array [1..10] of integer;
    p:integer;

// v zozname najde k-ticu s najvacsim suctom prvkov
function kTica(k:integer; zoznam:TZoznam):TVysledok;
var vysledok:TVysledok;
    maximum,pomocne_maximum,i,j,n:integer;
begin
  vysledok.zoznam.pocet:=k;
  maximum:=0;
  for n:=1 to k do begin vysledok.zoznam.pole[n]:=zoznam.pole[n];
                          maximum:=maximum+zoznam.pole[n];
                   end;
  for i:=2 to zoznam.pocet-k do begin
    pomocne_maximum:=0;
    for j:=1 to k do
      pomocne_maximum:=pomocne_maximum+zoznam.pole[j+i-1];
    if pomocne_maximum>maximum then begin
      maximum:=pomocne_maximum;
      for n:=1 to k do vysledok.zoznam.pole[n]:=zoznam.pole[n+i-1];
    end;
  end;
  vysledok.sucet:=maximum;
  kTica:=vysledok;
end;

// v transf najde k-ticu s najvacsim suctom prvkov
function kTica2(k:integer; transf:TTransf):TVysledok;
var vysledok:TVysledok;
    m,mm,i,j,n, index:integer;
begin
  vysledok.zoznam.pocet:=k;
  m:=0;
  for n:=1 to k do begin vysledok.zoznam.pole[n]:=transf.sucty[n];
                         m:=m+transf.sucty[n];
                         index:=1;
                         vysledok.zaciatok:=1;
                         vysledok.koniec:=k;

                   end;
  for i:=2 to transf.pocet-k do begin
      if i mod 2 = 0 then begin
        mm:=0;
        for j:=1 to k do
          mm:=mm+transf.sucty[j+i];
        if mm>m then begin
          m:=mm;
          for n:=1 to k do vysledok.zoznam.pole[n]:=transf.sucty[n+i];
          vysledok.zaciatok:=i+1;
          vysledok.koniec:=i+k;
        end;
      end;
  end;
  vysledok.sucet:=m;
  kTica2:=vysledok;
end;

// transformuje zoznam na transf - scita za sebou iduce kladne a zaporne cisla, zaporne cisla na okrajoch
//  sa neberu do uvahy
function transformuj(zoznam:TZoznam):TTransf;
var i,j,k,m:integer;
    zaporne, kladne:integer;
    transf:TTransf;
begin
  i:=1;
  k:=1;
  while i<=zoznam.pocet do begin
    kladne:=0; zaporne:=0; j:=i;
    // hladame za sebou iduce zaporne cisla
    while ((i<=zoznam.pocet) and (zoznam.pole[i]<0)) do begin zaporne:=zaporne+zoznam.pole[i]; i:=i+1; end;
    // zaporne cisla na zaciaku a na konci zoznamu nas nezaujimaju
    if (zaporne<>0) and (k>1) and (i<zoznam.pocet) then begin
      transf.sucty[k]:=zaporne;
      // skopirujeme dotycne za sebou iduce zaporne cisla do transf
      for m:=1 to i-j do
        transf.casti[k].pole[m]:=zoznam.pole[j+m-1];
      transf.casti[k].pocet:=i-j;
      k:=k+1;
    end;
    j:=i;
    // hladame za sebou iduce kladne cisla
    while ((i<=zoznam.pocet) and (zoznam.pole[i]>0)) do begin kladne:=kladne+zoznam.pole[i]; i:=i+1; end;
    if kladne<>0 then begin
      transf.sucty[k]:=kladne;
      // skopirujeme dotycne za sebou iduce kladne cisla do transf
      for m:=1 to i-j do
        transf.casti[k].pole[m]:=zoznam.pole[j+m-1];
      transf.casti[k].pocet:=i-j;
      k:=k+1;
    end;
  end;
  k:=k-1;
  transf.pocet:=k;
  transformuj:=transf;
end;

// prejde cez transf len raz a potom vrati vysledok
// len zisti sucet pre postupnost s najvacsim suctom
//(v pripade vypisovania postupnosti by sa znizila prehladnost,
// teraz je to celkom jednoduche)
function hladaj(transf:TTransf):integer;
var suma, maxsuma:integer;
    i:integer;
begin

  suma:=transf.sucty[1];
  maxsuma:=transf.sucty[1];
  i:=2;
  while i<=transf.pocet do begin
      if transf.sucty[i]+suma<0 then begin
        i := i+1;
        suma:=transf.sucty[i];
        i:=i+1;
        if maxsuma<suma then maxsuma:=suma;
      end
      else begin
          suma:=suma+transf.sucty[i];
          i := i+1;
        if maxsuma<suma then maxsuma:=suma;
      end;
  end;
  hladaj:= maxsuma;
end;



var z,z2:TVysledok;
    i,j,m,maximum,index,k:integer;
    transf: TTransf;

begin
  // prehladanie vsetkych postupnosti dlzky 1 az pocet
  writeln('a');
  maximum:=0;
  for i:=1 to zoznam.pocet do begin
    z:=kTica(i, zoznam);
    write(z.sucet:3,':');
   for j:=1 to z.zoznam.pocet do write(z.zoznam.pole[j]:3);
   if maximum<z.sucet then begin maximum:=z.sucet; index:=i; z2:=z end;
    writeln;
  end;
  write('Najvacsia postupnost ',maximum,':');
  for j:=1 to z2.zoznam.pocet do write(z2.zoznam.pole[j]:3);
  writeln;
  writeln;

  //1. zrychlenie
  //najprv transformujme
  transf:=transformuj(zoznam);
  // vypisme si strukturu transf
  for i:=1 to transf.pocet do begin
    write(transf.sucty[i]:4,' / ');
    for m:=1 to transf.casti[i].pocet do
      write(transf.casti[i].pole[m]:4);
    writeln;
  end;
  writeln;

  maximum:=0;
  for i:=1 to transf.pocet do begin
    if (i mod 2 = 1) then begin
      z:=kTica2(i,transf);
      write(z.sucet:3,':');
      for j:=1 to z.zoznam.pocet do write(z.zoznam.pole[j]:4);
      write(', zoznam: ');
      for j:=z.zaciatok to z.zaciatok+i do
        for m:=1 to transf.casti[j].pocet do
          write(transf.casti[j].pole[m]:3);
      if maximum<z.sucet then begin maximum:=z.sucet; index:=i; z2:=z end;
      writeln;
    end;
  end;
  write('Najvacsia postupnost ',maximum,':');
  for j:=1 to z2.zoznam.pocet do write(z2.zoznam.pole[j]:3);
  write(', zoznam: ');
  for j:=z2.zaciatok to z2.zaciatok+index do
    for m:=1 to transf.casti[j].pocet do
      write(transf.casti[j].pole[m]:3);
  writeln;
  writeln;
  writeln(hladaj(transf));



  readln;
end.