Tengo una matriz de números, ahora tengo que encontrar la suma de los elementos generando todos los subarreglos posibles de la matriz dada y aplicando algunas condiciones.
La condición es que cada subarreglo obtenga el minimum y también encuentre el total of elements en él y multiplique ambos (minimum * total) . Finalmente, add todos estos valores multiplicados para todos los subarreglos.
Aquí está el enunciado del problema:
Encuentre la suma de todos los subconjuntos posibles utilizando la siguiente fórmula:
Sum(left, right) = (min of arr[i]) * (∑ arr[i]), donde i varía de izquierda a derecha.
Ejemplo:
Array = [2,3,2,1]Los subconjuntos son: [start_index, end_index]
[0,0] subarray = [2], min is 2 and total of items = 2. min * total = 2*2=4 [0,1] subarray = [2,3], min is 2 and total of items = 5. min * total = 2*5=10 [0,2] subarray = [2,3,2], min is 2 and total of items = 7. min * total = 2*7=14 [0,3] subarray = [2,3,2,1], min is 1 and total of items = 8. min * total = 1*8=8 [1,1] subarray = [3], min is 3 and total of items = 3. min * total = 3*3 = 9 [1,2] subarray = [3,2], min is 2 and total of items = 5. min * total = 2*5 = 10 [1,3] subarray = [3,2,1], min is 1 and total of items = 6. min * total = 1*6 = 6 [2,2] subarray = [2], min is 2 and total of items = 2. min * total = 2*2 = 4 [2,3] subarray = [2,1], min is 1 and total of items = 3. min * total = 1*3 = 3 [3,3] subarray = [1], min is 1 and total of items = 1. min * total = 1*1 = 1 Total = 4 + 10 + 14 + 8 + 9 + 10+ 6 + 4 + 3 + 1 = 69Así que la respuesta es 69 en este caso.
Restricciones:
Each array element is in range 1 to 10^9. Array size 1 to 10^5. Return response in modulo 10^9+7Este es el código que probé.
public static int process(List<Integer> list) { int n = list.size(); int mod = 7 + 1000_000_000; long result = 0; for (int i = 0; i < n; i++) { long total = 0; int min = list.get(i); for (int j = i; j < n; j++) { int p = list.get(j); total = (total + p) % mod; min = Math.min(min, p); result = (result + (min * total) % mod) % mod; } } return (int) result; }¿Quiero reducir la complejidad temporal de este algoritmo?
¿Cuál puede ser un mejor enfoque para resolver esta tarea?
Actualizar:
David Eisenstat ha dado una gran respuesta, pero me resulta difícil de entender y vengo con un programa Java, ¿alguien puede proporcionar una solución Java para el enfoque o proporcionar un pseudocódigo para que pueda crear un programa?
Su solución actual tiene complejidad de tiempo O(n^2) , asumiendo que list.get es O(1) . Hay exactamente 1 + 2 + ... + n-1 + n operaciones que se pueden expresar como n * (n + 1)/2 , por lo tanto, O(n^2) .
Curiosamente, n * (n + 1)/2 es la cantidad de subconjuntos que puede obtener de un conjunto de longitud n , como se define en su pregunta y es evidente en su código.
Esto implica que está realizando una operación por subconjunto y estas son las operaciones mínimas requeridas para esta tarea, ya que debe mirar al menos una vez en cada subconjunto.
Mi conclusión es que no es posible reducir la complejidad temporal de esta tarea, a menos que exista alguna fórmula matemática que ayude a hacerlo.
Esto no significa necesariamente que no haya formas de optimizar el código, pero eso necesitaría pruebas y puede ser específico del idioma. Independientemente, no cambiaría la complejidad del tiempo en términos de n donde n es la longitud de la matriz de entrada.
Agradezco cualquier entrada en mi lógica. Estoy aprendiendo yo mismo.
La respuesta proporcionada por David Eisenstat es muy eficiente con una complejidad de O(n) .
Me gustaría compartir otro enfoque, que aunque tiene una complejidad de tiempo de O(n^2) , puede ser más simple y puede ser más fácil de entender para algunos (incluido yo).
matrix[n][n] , cada celda contendrá un par de Integers <sum, min> . denotaremos para cada Matrix[i, j] el primer elemento del par como Matrix[i, j].sum y el segundo como Matrix[i, j].min for i in [0, n-1]: Matrix[i][i] = <arr[i], arr[i]> for i in [0, n-1]: for j in[i, n-1]: Matrix[i, j] = < Matrix[i - 1, j].sum + arr[i, j], Min(Matrix[i - 1, j].min, arr[i, j]) > result = 0 for i in [0, n-1]: for j in[i, n-1]: result += Matrix[i, j].sum * Matrix[i, j].min Paso 1: iniciar una matriz bidimensional de tamaño [n,n] tomará en teoría O (n ^ 2) ya que puede requerir iniciar todos los índices en 0, pero si omitimos la inicialización de cada celda y solo asignamos la memoria esto podría tomar O(1)
Paso 2: aquí iteramos de 0 a n-1 haciendo un trabajo constante en cada iteración y, por lo tanto, la complejidad del tiempo es O(n)
Paso 3: aquí iteramos más de la mitad de las celdas de la matriz (todas las que están a la derecha de la diagonal), haciendo un trabajo constante en cada iteración y, por lo tanto, la complejidad del tiempo es O((n - 1) + (n - 2) + .... + (1) + (0)) = O(n^2)
Paso 4: Análisis similar al paso 3, O(n^2)
En total obtenemos O(n^2)
Este es un ejemplo simple del enfoque de programación dinámica.
Definamos sub[i, j] como el subarreglo entre el índice i y j mientras que 0 =< i, j <= n-1
Luego:
Matrix[i, j].sum = sum x in sub[i, j]Matrix[i, j].min = min x in sub[i, j]¿Por qué?
para sub[i,i] es obvio que:
Tal como lo calculamos en el paso 2.
Convéncete de que:
sum sub[i,j] = sum sub[i-1,j] + arr[i, j]min sub[i,j] = Min(min sub[i-1,j], arr[i, j])Esto explica el paso 3.
En el Paso 4 simplemente sumamos todo para obtener el resultado requerido.