Cod sursa(job #1363135)
Utilizator | hahahalera alexandru94 | Data | 26 februarie 2015 19:00:32 |
---|---|---|---|
Problema | Subsecventa de suma maxima | Scor | 85 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <iostream>
#include <fstream>
using namespace std;
int N, s[6000000];
ifstream in("ssm.in");
ofstream out("ssm.out");
int main()
{
int i, s_min = 0, s_max = -int(2e9), ind = 0, start, end;
in >> N;
for(i = 1; i <= N; i++)
{
in >> s[i];
}
/* magic here*/
for(i = 2; i <= N; i++)
{
s[i] = s[i - 1] + s[i];
if(s_max < s[i] - s_min ) {
s_max = s[i] - s_min;
start = ind + 1;
end = i;
}
if(s_min > s[i]) {
s_min = s[i];
ind = i;
}
}
out<< s_max << " " <<start<< " " << end;
return 0;
}