Cod sursa(job #743311)
Utilizator | Stavarache Petru Eric ericpts | Data | 3 mai 2012 21:44:11 |
---|---|---|---|
Problema | Subsecventa de suma maxima | Scor | 95 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.26 kb |
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream in("ssm.in");
ofstream out("ssm.out");
int pos1,pos2,S,n;
long long suma_cr,suma_mx;
in >> n;
in >> S;
suma_cr = suma_mx = S;
pos1 = pos2 = 1;
int a_pos1 = 1;
for(int i = 2;i<=n;i++)
{
in >> S;
if(S<0)
{
if(suma_cr > suma_mx)
{
pos1 = a_pos1;
pos2 = i-1;
suma_mx = suma_cr;
}
if(S>suma_cr)
{
a_pos1 = i;
suma_cr = S;
}
else
suma_cr+=S;
}
else
{
if(suma_cr > suma_mx)
{
pos1 = a_pos1;
pos2 = i-1;
suma_mx = suma_cr;
}
if(S+suma_cr > S)
{
suma_cr+=S;
}
else
{
suma_cr = S;
a_pos1 = i;
}
}
}
if(suma_cr > suma_mx)
{
suma_mx = suma_cr;
pos2 = n;
pos1 = a_pos1;
}
out << suma_mx << " " << pos1 << " " << pos2;
return 0;
}