Supongamos que la matriz es A={1,2,3} , ahora obtenga todos los subarreglos para esta matriz. Para cada subarreglo, encuentre el mínimo en ese subarreglo, también encuentre la suma de elementos en ese subarreglo. Finalmente suma todos estos valores. La entrada no se puede ordenar porque quiero todos los subarreglos posibles.
Ejemplo:
Los posibles subconjuntos son:
{1} - min = 1, sum = 1 => min* sum = 1 {1,2} - min = 1, sum = 3 => min* sum = 3 {1,2,3} - min = 1, sum = 6 => min* sum = 6 {2} - min = 2, sum = 2 => min* sum = 4 {2,3} - min = 2, sum = 5 => min* sum = 10 {3} - min = 3, sum = 3 => min* sum = 9Finalmente suma todos estos valores para obtener el resultado = 1 + 3 + 6 + 4 + 10 + 9 = 33.
Restricciones: los elementos de la matriz pueden variar de 1 a 1000_000_000. Tamaño de matriz de 1 a 100_000. Salida de retorno como módulo 7+1000_000_000.
Aquí está mi programa con O(n^2). Quiero un mejor algoritmo con menor complejidad de tiempo.
public int program(int[] A, int n) { int M = 7 + 1000_000_000; long total = 0; for (int i = 0; i < n; i++) { long sum = 0; int min = A[i]; for (int j = i; j < n; j++) { int a = A[j]; sum= (sum + a) % M; min = Math.min(min, a); total = (total + (min * sum) % M) % M; } } return (int) total; }Rango de entrada:
n range is 1 to 10^6 elements in array range is 1 to 10^9puedes intentar usar la recursividad.
int[] array = {1,2,3}; int maxSum = totalOfSubArray(array, 0, 0); private static int totalOfSubArray(int[] arr, int currentIndex, int maxSum) { int currentSum = 0; if (currentIndex == arr.length) { System.out.println("final total: " + maxSum); return maxSum; } String result = ""; for (int i = currentIndex; i < arr.length; i++) { result += arr[i]; currentSum += arr[i]; int min = Math.min(arr[currentIndex], arr[i]); maxSum += min * currentSum; System.out.println("[" + result + "] min : " + min + " currentSum: " + currentSum + " maxSum: " + maxSum); } return totalOfSubArray(arr, currentIndex + 1, maxSum); }