Cod sursa(job #873445)

Utilizator petiVass Peter peti Data 7 februarie 2013 11:28:15
Problema Subsecventa de suma maxima Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <limits>

using namespace std;

int main()
{
    ifstream ifs("ssm.in");
    ofstream ofs("ssm.out");

    int N;
    ifs>>N;
    int *m=new int[N];

    for(int i=0;i<N;i++)
        ifs>>m[i];

    int *best=new int[N];
    int maxsum=0;
    int l=0,r=0;
    best[0]=m[0];
    for(int i=1;i<N;i++){
        int tmp=best[i-1]+m[i];


        if(m[i]<tmp){
            best[i]=tmp;
            if(best[i]>maxsum)
               r=i;
        }

        if(m[i]>tmp && tmp!=0){
            best[i]=m[i];
            if(best[i]>maxsum)
               l=i;
        }
        if(m[i]==tmp){
            best[i]=tmp;
            if(best[i]>maxsum)
               l=i-1;
        }

        if(best[i]>maxsum)
            maxsum=best[i];

   }


    cout<<"l "<<l+1<<"\n";
    cout<<"r "<<r+1<<"\n";
    cout<<"m "<<maxsum<<"\n";
    ofs<<maxsum<<" "<<l+1<<" "<<r+1;
    return 0;
}