Cod sursa(job #1082659)
| Utilizator | Data | 14 ianuarie 2014 20:52:01 | |
|---|---|---|---|
| Problema | Subsecventa de suma maxima | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.78 kb |
#include <fstream>
using namespace std;
ifstream in ("ssm.in");
ofstream out ("ssm.out");
int v[6000001];
int s[6000001];
int main()
{
int n, sum, i,j, smax, ic, jc, ia;
in>>n;
s[0]=0;
for(j=1; j<=n; j++)
{
in>>v[j];
s[j]=s[j-1]+v[j];
}
smax=v[1];
i=1;
ic=1;
jc=1;
for(j=2; j<=n; j++)
{
ia=i;
if(s[i]>s[j])
i=j;
if(i+1<=j)
{
sum=s[j]-s[i];
if(sum>smax)
{
smax=sum;
ic=i+1;
jc=j;
}
}
else
{
sum=s[j]-s[ia];
if(sum>smax)
{
smax=sum;
ic=ia+1;
jc=j;
}
}
}
out<<smax<<" "<<ic<<" "<<jc;
return 0;
}
