Cod sursa(job #2721870)

Utilizator maraboneaMara Bonea marabonea Data 12 martie 2021 12:58:48
Problema SequenceQuery Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
/**
*/
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int nmax=100010;
int n,x[nmax],dp,poz1,poz2,sum,m,k,a,b,suma=-100010;
void solve(int s,int fin)
{
    m=1;
    for(int i=s;i<=fin;i++)
    {
        dp=dp+x[i];
        if(dp>sum)
        {
            sum=dp;
            poz1=m;
            poz2=i;
        }
        if(dp<0)
        {
            dp=0;
            m=i+1;
        }
    }
     fout<<sum<<endl;
}
int nr(int c,int d)
{
    for(int i=c;i<=d;i++)
    {
        if(x[i]>0)
            return 0;
        if(x[i]>suma)
            suma=x[i];
    }
    return 1;
}
void read()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        fin>>x[i];
    }
    while(k)
    {
        fin>>a>>b;
        m=1;
        sum=0;
        suma=-100010;
        dp=0;
        if(nr(a,b)==1)
            fout<<suma<<endl;
        else
            solve(a,b);
        k--;
    }
}

int main()
{
    read();

   return 0;
}