Cod sursa(job #2121396)

Utilizator omegasFilip Ion omegas Data 3 februarie 2018 17:27:15
Problema Subsecventa de suma maxima Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("ssm.in");
ofstream fout("ssm.out");
using namespace std;


int v[600100];
int best;

struct seq{
int left;
int right;
int sum;
};





int main()
{
    int n,i;
    fin >> n;
    for(i=1;i<=n;++i){
        fin >> v[i];
    }

    seq smax, best;
    smax.left = smax.right = 1;
    smax.sum = v[1];
    best.left = best.right = 1;
    best.sum = v[1];

    for(i=2;i<=n;++i){
        if(v[i] < v[i] + best.sum)
            best.sum += v[i],
            best.right++;
        else
            best.left = best.right = i,
            best.sum = v[i];

        if(smax.sum < best.sum)
            smax.sum = best.sum,
            smax.left = best.left,
            smax.right = best.right;
    }

    fout << smax.sum <<" "<< smax.left <<" "<< smax.right;





    return 0;
}