Cod sursa(job #1130510)

Utilizator lucianRRuscanu Lucian lucianR Data 28 februarie 2014 13:44:31
Problema Subsecventa de suma maxima Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#define N_MAX 6000010

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

int n, s[N_MAX], sum[N_MAX], best[N_MAX], best_sum, imin[N_MAX], imax;

int smin(int i)
{
    int mins = s[1];
    for(int j = 0; j < i; j++)
        if(mins > sum[j]) { mins = sum[j]; imin[i] = j + 1; }
    return mins;
}

int main()
{
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        in >> s[i];
        sum[i] = sum[i - 1] + s[i];
    }
    imin[1] = 1;
    imin[0] = 1;
    for(int i = 2; i <= n; i++)
    {
        best[i] = sum[i] - smin(i);
        if(best[best_sum] < best[i]){ best_sum = i; imax = i; }
    }
    out << best[best_sum] << " " << imin[best_sum] << " " << imax;
    return 0;
}