Pagini recente » Cod sursa (job #1707302) | Cod sursa (job #1288561) | Cod sursa (job #1753743) | Cod sursa (job #847210) | Cod sursa (job #1666326)
#include <stdio.h>
#define MAX_N 50000
#define INFINIT 2000000000
int sp[ 1 + MAX_N ];
int main() {
int n , k , i , x , rez , fMax , lMax , first , min;
FILE *fin = fopen( "secv2.in" , "r" );
fscanf( fin , "%d%d" , &n , &k );
rez = -INFINIT;
min = 0;
first = 0;
fMax = lMax = 0;
for( i = 1; i <= n ; i++ ) {
fscanf( fin , "%d" , &x );
//sumele partiale pana la pozitia curenta
sp[ i ] = sp[ i - 1 ] + x;
//avem macar o subsecventa completa
if( i >= k ) {
//cautam suma partiala minima din afara subsecventei; de asemenea tb sa fie si negativa
if( sp[ i - k ] < min ) {
min = sp[ i - k ];
first = i - k;
}
//diferenta dintre suma partiala curenta si cea minima gasita va fi o subsecventa de lung cel putin k
//iar suma ei va fi cat se poate de mare
//maximul dintre aceste subsecvente va fi raspunsul
if( sp[ i ] - min > rez ) {
rez = sp[ i ] - min;
fMax = first + 1;
lMax = i;
}
}
}
fclose( fin );
FILE *fout = fopen( "secv2.out" , "w" );
fprintf( fout , "%d %d %d" , fMax , lMax , rez );
fclose( fout );
return 0;
}