Cod sursa(job #1666326)

Utilizator TincaMateiTinca Matei TincaMatei Data 27 martie 2016 21:46:37
Problema Secventa 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.16 kb
#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;
}