Cod sursa(job #2278500)

Utilizator TooHappyMarchitan Teodor TooHappy Data 8 noiembrie 2018 09:20:03
Problema Subsecventa de suma maxima Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("ssm.in");
ofstream out("ssm.out");

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int n; in >> n;

    vector< int > v(n + 1, 0);
    for(int i = 1; i <= n; ++i) {
        in >> v[i];
    }

    int bestSum = v[1], bestI = 1, bestJ = 1;
    pair< int, int > minSumSoFar = {v[1], 1};

    for(int i = 2; i <= n; ++i) {
        v[i] += v[i - 1];

        if(v[i] - minSumSoFar.first > bestSum) {
            bestSum = v[i] - minSumSoFar.first;
            bestI = minSumSoFar.second;
            bestJ = i;
        }

        minSumSoFar = min(minSumSoFar, {v[i], i});
    }

    out << bestSum << " " << bestI + 1 << " " << bestJ << "\n";

    in.close(); out.close();
 
    return 0;
}