Cod sursa(job #2849289)

Utilizator TeodorVTeodorV TeodorV Data 14 februarie 2022 20:18:33
Problema Subsecventa de suma maxima Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[6000001],a[6000001];

int main()
{
    int n,x;
    fin>>n>>x;
    int v[n+1]={0};
    v[1]=x;
    for(int i=2; i<=n; i++)
    {
          fin>>x;
          v[i]=v[i-1]+x;
    }
    int a[n+1]={0};
    for(int i=1; i<=n; i++)
    {
        if(v[i-1]<v[a[i-1]])
            a[i]=i-1;
        else a[i]=a[i-1];
    }
    int vmax=v[1],max_st=1,max_dr=1;
    for(int dr=1; dr<=n; dr++)
    {
        int st=a[dr]+1;
        int sum=v[dr]-v[st-1];
        if(sum>vmax)
        {
            vmax=sum;
            max_st=st;
            max_dr=dr;
        }
    }
    fout<<vmax<<' '<<max_st<<' '<<max_dr;
    return 0;
}