
Tabla de contenidos
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 unint
. 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 demaxSum
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 acurrentSum
y se actualizamaxSum
sicurrentSum
es mayor quemaxSum
. SicurrentSum
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 matrizdp
.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.