Este algoritmo es relativamente conocido, también se le conoce como máxima subsuma.

Su enunciado es el siguiente:

Dado un vector, o arreglo de números enteros con longitud m, hallar un sub-vector, es decir un arreglo dentro de él, de longitud n que nos arroje como resultado la máxima suma de sus elementos, donde m >= n.

Por ejemplo en el vector: [1,2,-4,3,3,-1,2]

el subvector de suma máxima sería [3,3,-1,2] y la suma sería 7. Esto es así ya que si añadimos 1,2 o -4 sólo conseguiríamos reducir la suma.

Ahora a resolverlo utilizando C#

        public static int MaximaSubSuma(int[] vector)
        {
            int suma = 0;
            int maxSum = 0;

            for(int i = 0; i < vector.Length; i++)
            {
                for(int j = i; j < vector.Length; j++)
                {
                    suma += vector[j];

                    if(suma > maxSum)
                        maxSum = suma;
                }
                suma = 0;
            }
            return maxSum;
        }

Debido a que quiero probar todo tipo de combinaciones consecutivas, entonces debo hacer una iteración anidada en otra para capturar todas las combinaciones posibles y ayudarme de variables auxiliares.

Pongámoslo a prueba!

Lo haré utilizando un programa de consola

        static void Main(string[] args)
        {
            Console.WriteLine("Max subvector suma!");

            int[] lista = new int[] {1,2,-4,3,3,-1,2 };
            Console.WriteLine(MaximaSubSuma(lista));
        }

Genial, pues ya lo tienes crack!

Recuerda que esta entrada es de la serie de artículos Algoritmos notables, los cuales los subo a este repo, puedes visitarlo y descubrir más algoritmos 😊

Espero esta entrada te haya gustado, analiza el código y trata de optimizarlo.

Ah y no te olvides de compartir esta entrada en toditas tus redes 😉