Cod sursa(job #2786930)

Utilizator db_123Balaban David db_123 Data 21 octombrie 2021 23:47:51
Problema Subsecventa de suma maxima Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>

using namespace std;

ifstream cin("ssm.in");
ofstream cout("ssm.out");

const int DIM=1000;

int v[DIM]={0};
int sumP[DIM]={0};

int main()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>v[i];
    }

    sumP[0]=v[0];
    for(int i=1;i<n;i++){
        sumP[i]=sumP[i-1]+v[i];
    }

    /*for(int i=0;i<n;i++){
        cout<<sumP[i]<<" ";
    }
    return 0;*/

    int sumMax=0,sum=0,startPoint=0,endPoint=0;
    for(int i=0;i<n;i++){ ///verificam subsecvente de lungime 1
        //sumMax=max(sumMax,v[i]);
        if(sumMax<v[i]){
            startPoint=i;endPoint=i;
            sumMax=v[i];
        }
    }

    for(int i=1;i<n;i++){
        for(int j=i;j<n;j++){
            if(j-i==0){
                sum+=sumP[j];
            }
            else{
                sum+=(sumP[j]-sumP[j-i-1]);
            }
            //sumMax=max(sumMax,sum);
            if(sumMax<sum){
                startPoint=j-i;
                endPoint=j;
                sumMax=sum;
            }
            sum=0;
        }
    }

    cout<<sumMax<<" "<<startPoint+1<<" "<<endPoint+1;
    return 0;
}