Cod sursa(job #1240122)

Utilizator gabrieligabrieli gabrieli Data 10 octombrie 2014 16:00:11
Problema Subsecventa de suma maxima Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <iterator>
#include <algorithm>
#include <limits>
#include <functional>

using namespace std;

struct Solver {
    size_t left, right, start, current;
    int sum, maxim;
    
    Solver() : left(1), right(1), start(1), current(1), sum(0),
               maxim( numeric_limits<int>::lowest() ) {}
    
    void operator() (const int &x) {
        sum += x;

        if (sum > maxim) {
            maxim = sum;
            left = start;
            right = current;
        }

        if (sum < 0) {
            start = current + 1;
            sum = 0;
        }
        
        ++current;
    }
    
    void solution(ostream& out) {
        out << maxim << ' ' << left << ' ' << right << endl;
    }
} solve;

int main() {
    ifstream fin("ssm.in");
    ofstream fout("ssm.out");
    
    int n; fin >> n;
    
    for_each (istream_iterator<int> (fin), istream_iterator<int>(), ref(solve));
    solve.solution(fout); 
    
    return 0;
}