Interesting Sequences ( Programacion Dinamica y Barrido)

http://uva.onlinejudge.org/external/123/12385.html


Este problema se trata de dada una secuencia, encontrar una subsecuencia interesante, una subsecuencia interesante es una subsecuencia donde el primer elemento es igual al ultimo, y tu tarea es encontrar el maximo numero de subsecuencias de este tipo de tal manera que no se intersecten una con otra.

/* Autor: Rodrigo Burgos Dominguez */
#include "stdio.h"
#include "string.h"

#define MAXELEMENT 100000

int list[MAXELEMENT + 1];
int next[MAXELEMENT + 1];
int scanning[MAXELEMENT + 1];
int dp[ MAXELEMENT + 1];

int max( int a, int b){ return a > b ? a : b; }

main(){
  int cases, ncases, n, x;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
   scanf("%d", &n);
   for( x = 0; x < n; x++) scanf("%d", &list[ x ]);
   /* se inicializa el barrido, para indicar que ningun elemento del mismo tipo a sido encontrado */
   memset( scanning, -1, sizeof( scanning ));
   for( x = n - 1; x >= 0 ; x--){
    /* Se calcula el siguiente elemento igual a list[x] que encontro en el barrido ( scanning) */
       next[ x ] = scanning[ list[ x ] ]; 
       /* Se incerta al barrido que el elemento list[x] se encontro en la posicion x */
    scanning[ list[x] ] = x;
   }
   memset( dp, 0, sizeof( dp ));
   for( x = 0; x < n; x++){
    /* Si en la posicion x existe algun elemento igual a el pero despues de el, se puede incrementar 
       el numero de subsecuencias */
    if( next[x] != -1) dp[ next[x] ] = max( dp[ next[ x ]] , dp[ x ] + 1 );
    /* En dado caso de no encontrar ningua se asigna a la siguiente posicion el mejor valor obtenido*/
    dp[ x + 1] = max( dp[ x + 1], dp[ x ] );
   }
   printf("%d\n", dp[ n ]);
  }
  return 0; 
}