Cod sursa(job #2489907)

Utilizator PopDragosTheLamacorn PopDragos Data 9 noiembrie 2019 13:06:05
Problema Subsecventa de suma maxima Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;
int n,a[6000001],b[6000001], x, y, s,i=1,j;
int main()
{
    ifstream fin("ssm.in");
    ofstream fout("ssm.out");
    fin>>n;
    for(int k=1; k<=n; k++)
    {
        fin>>a[k];
        b[k]=b[k-1]+a[k];
        s+=a[k];

    }
    j=n;
    x = i;
    y = j;
    while(i<j)
    {
        if(b[i]>=b[j])
        {
            if(i==1)
            {
                if(b[j]>s)
                {
                    s=b[j];
                    x=i;
                    y=j;

                }
            }
            else
            {
                if(b[j]-b[i-1]>s)
                {
                    s=b[j]-b[i-1];
                    x=i;
                    y=j;

                }
            }
            j--;

        }
        if(b[i]<b[j])
        {
            if(b[j]-b[i-1]>s)
            {
                s=b[j]-b[i-1];
                x=i;
                y=j;
            }
            i++;
        }
    }

    fout<<s<<" "<<x<<" "<<y;



    return 0;
}