algorithm - reglas - Encuentra la longitud de secuencia más larga cuya suma es divisible por 3

numeros divisibles por 3

Question

Tengo un ejercicio que debe hacerse con O (n) complejidad de tiempo, sin embargo, solo puedo resolverlo con una solución O (n ^ 2)

Tiene una matriz y necesita contar la secuencia contigua más larga para que su suma se pueda dividir en 3 sin ningún resto. Por ejemplo, para la array {1,2,3,-4,-1) , la función devolverá 4 porque la secuencia más larga en que su sum(0) se puede dividir en 3 es {2,3,-4,-1} .

Mi solución O (n ^ 2) se basa en la arithmetic progression . ¿Hay alguna manera de hacerlo con O (n) complejidad?

Por favor, solo quiero una pista o una explicación teórica. Por favor, no escribas la solución completa :)

Answer 1

Como una persona que no es CS, esto es interesante. El primer enfoque mío fue simplemente calcular la suma corriente mod 3. Obtendrás una secuencia de {0,1,2}. Ahora busque el primer y el último 0, el primero y el último 1 y el primero y el último 2, y compare sus respectivas distancias ...

Answer 2

Echemos un vistazo a las sumas de prefijo. Un subarreglo [L, R] se divide por 3 si y solo si
prefixSum[L - 1] mod 3 = prefixSum[R] mod 3 . Esta observación proporciona una solución lineal muy simple (debido a que solo hay 3 valores posibles de un prefijo suma mod 3, simplemente podemos encontrar el primero y el último).

Por ejemplo, si la matriz de entrada es {1, 2, 3, -4, -1}, las sumas de prefijo son {0, 1, 0, 0, 2, 1}. (hay n + 1 sumas de prefijo debido a un prefijo vacío). Ahora solo puede echar un vistazo a la primera y última aparición de 0, 1 y 2.

Answer 3

Iterar a través de la matriz, sumando el total a medida que avanza. Registre la posición de la primera posición donde la suma del módulo es 0 . Además, registre la posición de la primera posición donde la suma del módulo es 1 . Y, finalmente, registre la posición de la primera posición donde la suma del módulo es 2 .

Haga lo mismo hacia atrás también, registrando la última posición donde la suma del módulo es 0 , 1 y 2 . Eso le da tres posibilidades para la secuencia más larga: simplemente marque qué par está más alejado.

Answer 4

Se aplica la programación dinámica. Por cada posición calculas 3 valores:

• La secuencia más larga que termina en esa posición que tiene suma s = 0 mod 3
• La secuencia más larga que termina en esa posición que tiene suma s = 1 mod 3
• La secuencia más larga que termina en esa posición que tiene suma s = 2 mod 3

Por lo tanto, dado este valor para la posición i, puede calcular fácilmente los nuevos para la posición i + 1.