Cod sursa(job #688664)
Utilizator | Cantor Paul Dan Cantor_paul | Data | 23 februarie 2012 18:49:34 |
---|---|---|---|
Problema | Subsecventa de suma maxima | Scor | 55 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.72 kb |
#include<algorithm>
#include<fstream>
using namespace std;
long n,a[600001];
int main()
{
ifstream f("ssm.in");
ofstream g ("ssm.out");
int i;
f>>n;
for(i=1;i<=n;i++)
f>>a[i];
long suma=-int(2e9),inceput,sfarsit,poz,max=0;
for(i=1;i<=n;i++)
{ if(suma>=0)
suma+=a[i];
else
{
suma=a[i];
poz=i;
}
if(suma>max)
{ max=suma;
inceput=poz;
sfarsit=i;
}
}
g<<max<<" "<<inceput<<" "<<sfarsit;
f.close();
g.close();
return 0;
}