Algoritmo de la subsecuencia de suma máxima

La subsecuencia de suma máxima

El problema de la subsecuencia de suma máxima consiste en encontrar la subsecuencia de una secuencia dada que tiene la suma máxima. Por ejemplo, dada la secuencia [-2, 1, -3, 4, -1, 2, 1, -5, 4], la subsecuencia de suma máxima es [4, -1, 2, 1], ya que su suma es 6.

A continuación se presenta un algoritmo en Java para resolver este problema:

Declara una variable maxSum inicializada en el valor mínimo posible de un int. Esta variable se utilizará para almacenar la suma máxima encontrada hasta el momento.
Recorre la secuencia elemento por elemento. En cada iteración del bucle, actualiza la variable maxSum comparando el valor actual de maxSum con la suma de la subsecuencia hasta el elemento actual.
Para calcular la suma de la subsecuencia hasta el elemento actual, se puede utilizar otra variable, llamada currentsum, inicializada en 0. En cada iteración del bucle, se añade el elemento actual a currentSum y se actualiza maxSum si currentSum es mayor que maxSum. Si currentSum es menor que 0, se debe reiniciar a 0, ya que cualquier subsecuencia que incluya elementos negativos siempre será menor que cualquier subsecuencia que no los incluya.

A continuación se muestra un ejemplo de código en Java que implementa este algoritmo:

				
					    public static int maxSumaMaxima(int[] arr) {
    
        // Inicializar la suma máxima y la suma actual con el primer elemento del Array
        int maxSum = arr[0];
        int currentSum = 0;
        
        // Recorrer el Array elemento por elemento
        for (int i = 0; i < arr.length; i++) {
            
            // Actualizar la suma actual sumándole el elemento actual
            currentSum += arr[i];
    
            // Si la suma actual es mayor que la suma máxima, actualizar la suma máxima
            maxSum = Math.max(maxSum, currentSum);
    
            // Si la suma actual es negativa, reiniciarla a 0
            if (currentSum < 0) {
                currentSum = 0;
            }
        }
        // Devolver la suma máxima encontrada
        return maxSum;
    }

Aplicando el algoritmo anterior, el proceso sería el siguiente:

Inicializamos max_sum a 0 y current_sum a 0.
Recorremos la secuencia elemento por elemento.
Añadimos el elemento actual (4) a current_sum, lo que da un valor de 4.
Como 4 es mayor que 0, actualizamos max_sum con el valor de current_sum, que es 4.
Añadimos el elemento actual (-3) a current_sum, lo que da un valor de 1.
Como 1 es mayor que 0, pero no es mayor que max_sum, no actualizamos max_sum.
Añadimos el elemento actual (5) a current_sum, lo que da un valor de 6.
Como 6 es mayor que max_sum, actualizamos max_sum con el valor de 6.
Añadimos el elemento actual (-2) a current_sum, lo que da un valor de 4.
Como 4 es mayor que 0, pero no es mayor que max_sum, no actualizamos max_sum.
Añadimos el elemento actual (1) a current_sum, lo que da un valor de 5.
Como 5 es mayor que max_sum, actualizamos max_sum con el valor de 5.
Devolvemos max_sum como resultado final, que es 6.

				
					    public static void main(String[] args) {
    int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = maxSumaMaxima(arr);
    System.out.println(maxSum); // Imprimirá 6
}

Para utilizar el algoritmo de la subsecuencia de suma máxima, solo necesita llamar a la función `maxSumSubsequence` con el Array que contiene la secuencia de números. La función devolverá la suma máxima de la subsecuencia encontrada. Es importante tener en cuenta que el algoritmo de la subsecuencia de suma máxima es muy eficiente y tiene un tiempo de ejecución de O(n), lo que significa que su rendimiento es lineal con respecto al tamaño de la secuencia. Esto lo convierte en una opción atractiva para resolver problemas que involucren la búsqueda de subsecuencias de suma máxima en secuencias de tamaño grande.

Implementación con programación dinámica

La programación dinámica es un enfoque para la resolución de problemas que consiste en dividir el problema en subproblemas más pequeños y almacenar los resultados de estos subproblemas para evitar tener que volver a calcularlos en el futuro.

En el caso del problema de la subsecuencia de suma máxima, podemos utilizar una matriz para almacenar los resultados parciales y evitar tener que volver a calcular la suma de subsecuencias que ya hemos evaluado.

A continuación se presenta un ejemplo de código en JAVA que implementa el algoritmo de la subsecuencia de suma máxima utilizando programación dinámica:

				
					public int maxSubsequenceSum(int[] sequence) {
    // Obtenemos el tamaño de la secuencia
    int n = sequence.length;
    // Creamos la matriz dp para almacenar los resultados parciales
    int[][] dp = new int[n][n];
    // Inicializamos la diagonal principal de la matriz dp con los valores de la secuencia original
    for (int i = 0; i < n; i++) {
        dp[i][i] = sequence[i];
    }
    // Recorremos todas las subsecuencias de longitud mayor que 1
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            // Calculamos el índice final de la subsecuencia actual
            int j = i + len - 1;
            // Actualizamos el valor de la matriz dp utilizando el resultado del subproblema anterior
            dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]) + sequence[j];
        }
    }
    // Buscamos la suma máxima de todas las subsecuencias
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        maxSum = Math.max(maxSum, dp[i][n - 1]);
    }
    // Devolvemos el resultado final
    return maxSum;
}

La matriz dp se utiliza para almacenar los resultados parciales de los subproblemas. Cada elemento de la matriz representa la suma máxima de una subsecuencia determinada, definida por su índice inicial y final.
El algoritmo se inicializa recorriendo la diagonal principal de la matriz dp y asignando a cada elemento de la matriz el valor del elemento correspondiente de la secuencia original. Esto se hace para asegurar que cada subsecuencia de longitud 1 tiene un valor correcto en la matriz dp.
A continuación, se recorren todas las subsecuencias de longitud mayor que 1 y se actualiza el valor de la matriz dp utilizando el resultado del subproblema anterior. Para ello, se utiliza un doble bucle anidado que recorre todas las subsecuencias de longitud mayor que 1.
Finalmente, se recorre la última fila de la matriz dp y se devuelve el máximo valor encontrado como resultado final. Esto se hace para encontrar la suma máxima de todas las subsecuencias posibles.

Comparando la complejidad de los algoritmos

El algoritmo de la subsecuencia de suma máxima presentado inicialmente tiene una complejidad temporal de O(n), donde n es el número de elementos de la secuencia, ya que se recorre la secuencia una única vez. Además, tiene una complejidad espacial de O(1), ya que sólo se utilizan variables adicionales para almacenar la suma máxima y la suma actual, independientemente del tamaño de la secuencia.

Por otro lado, el algoritmo de la subsecuencia de suma máxima implementado con programación dinámica tiene una complejidad temporal de O(n^2), donde n es el número de elementos de la secuencia, ya que se utiliza una matriz de tamaño n x n para almacenar los resultados parciales y se recorren todas las subsecuencias posibles para calcular los valores finales. Además, tiene una complejidad espacial de O(n^2), ya que la matriz utilizada para almacenar los resultados parciales también tiene un tamaño de n x n.

En general, el algoritmo de la subsecuencia de suma máxima implementado con programación dinámica es más lento y utiliza más espacio en memoria que el algoritmo inicial, esto es debido a la utilización de la matriz para almacenar los resultados parciales. Sin embargo, puede ser útil en casos en los que el problema se puede dividir en subproblemas que se pueden reutilizar en el futuro, ya que permite ahorrar tiempo al evitar tener que volver a calcular los resultados parciales.