Secventa

[•jurjstyle]

Problema suna in felul urmator: ,,Determinati o secventa de lungime k care are suma elementelor maxima dintr-un sir de n numere naturale".Daca exista 2 secvente de acest gen se va determina cea mai din stanga(prima).N,K si sirul se citesc din fisier.Numerele din fisier vor fi numere naturale,1<=k<=n<=100000.
Eu am rezolvat problema in O(N^2):

Cod:

#include<iostream>
#include<fstream>
using namespace std;
ifstream f("secvk.in");
ofstream g("secvk.out");
int v[100005];
int main()
{int n,k,i,st,dr,s,sfinal=0,j;
 f >> n >> k ;
 
 for(i=1;i<=n;++i)
   f >>v[i];
 for(i=1;i+k-1<=n;++i)
   {j=i;s=0;
    while(j<=i+k-1)
       {s=s+v[j];
        ++j;
       }
    if(s>sfinal) {sfinal=s;st=i;dr=j-1;}

   }
 for(i=st;i<=dr;++i)
   g<<v[i]<<" ";

f.close();
g.close();
}

Intrebarea mea este cum ar fi gandirea pentru o rezolvare mai rapida ?.

[•deneo]

Daca ai calculat suma secventei i -> i + k, atunci suma secventei i + 1 -> i + k + 1 e suma secventei anterioare + v[i + k + 1] - v [ i ] .
Bafta.

[•jurjstyle]

Mersi de idee.Am rescris problema si intra in timp dar e interesant ca imi pica un test care inainte nu-mi pica.O sa caut sa vad in ce caz pica.

Cod:

#include<iostream>
#include<fstream>
using namespace std;
ifstream f("secvk.in");
ofstream g("secvk.out");
int v[100005],s[100005];
int main()
{int n,k,i,st=0,dr=0,s1=0,sfinal=0,s2=0,j=1,var=0;
 f >> n >> k ;
for(i=1;i<=n;++i)
  f >>v[i];
i=1;
sfinal=v[1],st=i,dr=i+k-1;
for(i=1;i<=k;++i)
   s[j]=s[j]+v[i];
 if(s[j]>sfinal) sfinal=s[j],st=i,dr=i+k-1,var=1;

 ++j;
 for(i=2;i+k-1<=n;++i)
   {s[j]=s[j-1]+v[i+k-1]-v[i-1];

    if(s[j]>sfinal) sfinal=s[j],st=i,dr=i+k-1,var=1;
    ++j;
   }
if(var)
 for(i=st;i<=dr;++i)
   g <<v[i]<<" ";
   else for(i=st;i<=dr;++i)
          g <<v[i]<<" ";

f.close();
g.close();
}

EDIT:Pica cand k==n...

Cod:

#include<iostream>
#include<fstream>
using namespace std;
ifstream f("secvk.in");
ofstream g("secvk.out");
int v[100005],s[100005];
int main()
{int n,k,i,st=0,dr=0,s1=0,sfinal=0,s2=0,j=1,var=0;
f >> n >> k ;
for(i=1;i<=n;++i)
 f >>v[i];

for(i=1;i<=k;++i)
   s[j]=s[j]+v[i];
 if(s[j]>sfinal) sfinal=s[j],st=1,dr=k,var=1;

 ++j;
 for(i=2;i+k-1<=n;++i)
   {s[j]=s[j-1]+v[i+k-1]-v[i-1];

    if(s[j]>sfinal) sfinal=s[j],st=i,dr=i+k-1,var=1;
    ++j;
   }

for(i=st;i<=dr;++i)
   g <<v[i]<<" ";


f.close();
g.close();
}