Cod sursa(job #1089831)

Utilizator vlad96Vlad Zuga vlad96 Data 21 ianuarie 2014 23:06:08
Problema Subsecventa de suma maxima Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>

using namespace std;

int n, best[6000005], v[6000005], sum = -10000, st, dr, sti, dri;

inline void read ()
{
    FILE *fis = fopen ("ssm.in", "r");
    fscanf(fis, "%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        fscanf(fis, "%d", &v[i]);
    }
    fclose(fis);
}

inline void solve()
{
    st = 1;
    dr = 1;
    best[1] = v[1];
    for (int i = 2; i <= n; i ++ )
    {
        best[i] = v[i];
        dr = i;
        if ( best[i] < best[i-1] + v[i] )
        {
            best[i] = best[i-1] + v[i];
            dr = i;
        }
        else
            st = i;
        if ( best[i] > sum )
        {
            sum = best[i];
            dri = dr;
            sti = st;
        }
    }
}

inline void write ()
{
    FILE *fis2 = fopen ("ssm.out", "w");
    fprintf(fis2, "%d %d %d\n", sum, sti, dri);
    fclose(fis2);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}