Tengo un problema similar a este: https://stackoverflow.com/questions/3229459/algorithm-to-cover-maximal-number-of-points-with-one-circle-of-given-radius
De hecho os dejo un paint lamentable.
El problema en cuestión es dado un array de valores encontrar el subarray contiguo que cumpla que todos los valores incluidos sean menores que S.
Tengo una implementación naïve que es 0(n2)
Hay algo que no me queda claro y es el resultado. ¿Tiene que ser el subarray máximo? ¿Uno cualquiera?
#2 Si, el subarray máximo (start,end). Estoy ahora tratando de buscar una solución tipo dynnamic programming pero aún no lo acabo de conseguir.
#3 no se si estoy pasando algo por alto pero ¿no te sirve con recorrerlo solamente una vez y llevar dos contadores uno con el tamaño de subarray máximo encontrado hasta el momento y otro con el del tamaño que estés acutalmente + dos pares de índices uno par para el inicio/final del mejor encontrado hasta el momento y el otro par para el actual? En el momento que un número no cumpla compruebas si el actual es mayor que el mejor encontrado hasta el momento, si lo es actualizas y si no no, en ambos casos reseteando las variables del subarray actual.
Si lo entendí bien, es buscar la subsecuencia de elementos contiguos de mayor tamaño donde todos los elementos son menores que s. Se me ocurre algo como lo de #4, la verdad
#7 Entiendo que no, porque no haría falta recorrer los "vecinos" de cada elemento del array, es decir, tienes:
arr = [3,4,6,8,1,2,3]
s = 5
Lo habitual en estos casos es mirar desde i hasta que no se cumpla la condición y luego ir a i+=1. En este caso no hace falta, puedes saltar directamente a la posición donde encontraste el fallo (j por ejemplo), porque toda secuencia entre k con k>i y j va a tener menos elementos válidos en su interior que la secuencia entre i y j. De esta forma no necesitas bucles internos.
Supongo que no me he explicao xD
#7 Como va a ser n2?
arr = [...]
subMax = (ini = 0, fin = 0)
subCurr = (ini = 0, fin = 0)
por cada n en arr:
- n < S ?
- Sí -> subCurr.fin = pos
- No ->
subMax = max(subMax, subCurr)
subCurr = (pos, pos)
return max(subMax, subCurr)las funciones max y calcular el length (fin - ini) son constantes porque es una simple operación.
#8 es más, puedes paralizarlo casi de forma trivial. Ejemplo de dos hilos: miras el punto medio del array y te desplazas en una dirección hasta encontrar un número que no cumpla la condición y divides el trabajo.
Creo que me he explicado mal. Ya que vuestras soluciones omiten ciertos bucles internos (más bien el salto de vuestra ventana actual cuando deja de cumplir la condición es crear un nuevo actual que empieza donde se quedó la anterior cola. Es porque he definido mal la condición de que un punto esté dentro del intervalo. La condición de que un punto esté en el intervalo es que al calcular |max(sub)|-|min(sub)| <= S
Eso si, podemos tener el array inicial ordenado.
Hecho!! Luego dejo el código final.
