Cod sursa(job #2757257)

Utilizator danutbodbodnariuc danut danutbod Data 4 iunie 2021 18:55:42
Problema Subsecventa de suma maxima Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
////var I
//#include <fstream> //ordin de complexitate in timp
//using namespace std;      //O(n^3)
//ifstream fi("ssm.in");
//ofstream fo("ssm.out");
//long long  smaxi,s,p,k,u,i,n,j,a[6000001];
//
//int main()
//{
//    fi>>n;
//    for(i=1;i<=n;i++)fi>>a[i];
//    for(i=1;i<=n;i++)
//      for(j=i;j<=n;j++)
//        {
//            s=0;
//            for(k=i;k<=j;k++) s=s+a[k];
//            if(s>smaxi){smaxi=s;p=i;u=j;}
//        }
//    fo<<smaxi<<" "<<p<<" "<<u;
//    fo.close();fi.close();
//     return 0;
//}
//var II
#include <fstream> //ordin de complexitate in timp
using namespace std;      //O(n^2)
ifstream fi("ssm.in");
ofstream fo("ssm.out");
long long  smaxi,sum,p,k,u,i,n,j;
long long a[6000001],s[6000001];

int main()
{
    fi>>n;
    for(i=1;i<=n;i++)fi>>a[i];
    //calcul sume partiale
    for(i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    //
    for(i=1;i<=n;i++)
      for(j=i;j<=n;j++)
        {
            sum=s[j]-s[i-1];
            if(sum>smaxi){smaxi=sum;p=i;u=j;}
        }
    fo<<smaxi<<" "<<p<<" "<<u;
    fo.close();fi.close();
     return 0;
}