Cod sursa(job #1666313)

Utilizator TincaMateiTinca Matei TincaMatei Data 27 martie 2016 21:27:08
Problema Secventa 2 Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#define MAX_N 50000
#define INFINIT 2000000000

int suma[ 1 + MAX_N ] , sp[ 1 + MAX_N ];

int main() {
  int n , k , i , x , rez , first , fMax , lMax;
  FILE *fin = fopen( "secv2.in" , "r" );
  fscanf( fin , "%d%d" , &n , &k );
  
  rez = -INFINIT;
  for( i = 1; i <= n ; i++ ) {
    fscanf( fin , "%d" , &x );
    //sumele partiale pana la pozitia curenta
    sp[ i ] = sp[ i - 1 ] + x;
    if( i <= k ) //nu avem o subsecventa completa
      suma[ i ] = sp[ i ];
    else { // avem o subsecventa completa
      if( suma[ i - 1 ] + x < sp[ i ] - sp[ i - k ] ) { //vedem care e maxima si calculam capetele
        suma[ i ] = sp[ i ] - sp[ i - k ];
        first = i - k + 1;
      } else
        suma[ i ] = suma[ i - 1 ] + x;
        
      if( suma[ i ] > rez ) { //vedem daca este maxima
        rez = suma[ i ];
        fMax = first;
        lMax = i;
      }
    }
  }
  
  fclose( fin );

  FILE *fout = fopen( "secv2.out" , "w" );
  fprintf( fout , "%d %d %d" , fMax , lMax , rez );
  fclose( fout );
  return 0;
}