Me hicieron esta pregunta en una de mis entrevistas. Dada una matriz de números enteros ( con valores tanto positivos como negativos ), necesitamos encontrar el número máximo de subarreglos disjuntos que tengan la misma suma .

Ejemplo :

Entrada: [1, 2, 3] Salida: 2 {ya que tenemos como máximo 2 subarreglos con suma = 3, es decir, [1, 2], [3]}

Entrada: [2 2 2 -2] Salida: 2 {dos subarreglos cada uno con suma = 2, es decir, [2], [2, 2, -2]}

Mi acercamiento

El primer enfoque que me vino a la mente fue encontrar la matriz de suma de prefijos y luego tomar cada elemento (prefijo [i]) como objetivo para encontrar el número de subarreglos con suma = prefijo [i] .

Pero esto falló en el caso de los números negativos. ¿Cómo manejar los casos negativos?

EDITAR La matriz completa debe cubrirse con estas subarreglas. Es por eso que en el ejemplo 2 obtenemos 2 como salida y no 3 ([2],[2],[2]).