Cod sursa(job #1555788)

Utilizator valentin50517Vozian Valentin valentin50517 Data 23 decembrie 2015 15:54:57
Problema Subsecventa de suma maxima Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <algorithm>

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

int N,K,A[100100],dp[100100],pre[100100],preM[100100],poz[100100],maxi;
int main(){
    fin >> N;
    for(int i = 1;i<=N;i++){
           fin >> A[i];
           A[i]-=K;
           pre[i] = pre[i-1] + A[i]; 
           if(preM[i-1] > pre[i]){
                        poz[i] = i;
                        preM[i] = pre[i];             
           }else{
                 poz[i] = poz[i-1];
                 preM[i] = preM[i-1];
           }
    }
    
    for(int i = 1;i<=N;i++)
            dp[i] = pre[i] - preM[i];
    
    int rs = 0;
    for(int i = 0;i<=N;i++) if(rs < dp[i]) rs = dp[i],maxi = i;
    fout << dp[maxi] << ' '<< poz[maxi]+1 <<' ' << maxi;
    
    return 0;    
}