Algoritmo de Kadane [Codigo en C++]

Cuantas veces no nos hemos topado con un ejercicio para encontrar el maximo sub arreglo, bueno para que el tiempo de ejecucion de nuestro programa sea O(n) utlizaremos el algoritmo de Kadane.

Por Ejemplo Si Tenemos el Siguiente Arreglo :

ARREGLO = { - 4 , 10 , -1 , 8}

Entonces sus Sub Arreglos Seran :

SUBARREGLOS :

Entonces la Suma del Maximo SubArreglo sera :

ALGORITMO:

Kadane (Arreglo,tamaño)

Inicializamos :
   mayor : 0
                       mayor_temporal : 0
Para (Recorremos el arreglo desde 0 hasta N-1)
    mayor_temporal = mayor_temporal + Arreglo[i]
       si (mayor_temporal < 0 )
           mayor_temporal = 0
    fin de si

       si (mayor < mayor_temporal)
            mayor = mayor_temporal
fin de si
fin de Para
Retornar mayor

Empezaremos con un ejemplo :

Arreglo : {-2, 4, -1}
Tamaño :3
Inicio : (mayor , mayor_temporal ) = (0,0)

1ra pasada :

Para i = 0 , Arreglo [0] = -2
mayor_temporal = 0 + -2

si (mayor_temporal < 0) // -2 < 0
mayor_temporal = 0

        si (mayor < mayor_temporal) // 0 < 0
            mayor = mayor_temporal

        Los valores quedarian asi : (mayor , mayor_temporal ) = (0,0)

2da pasada :

Para i = 0 , Arreglo [1] =4
mayor_temporal = 0+ 4

si (mayor_temporal < 0) // 4 < 0
mayor_temporal = 0

        si (mayor < mayor_temporal) // 0 < 4
            mayor = mayor_temporal

        Los valores quedarian asi : (mayor , mayor_temporal ) = (4,4)

3ra pasada :

Para i = 0 , Arreglo [2] =-1
mayor_temporal = 4 + - 1

si (mayor_temporal < 0) // 3 < 0
mayor_temporal = 0

        si (mayor < mayor_temporal) // 4 < 3
            mayor = mayor_temporal

        Los valores quedarian asi : (mayor , mayor_temporal ) = (4,3)

RETORNA mayor = 4

CODIGO:

#include<stdio.h>
#define MAX 10000


int *ingresar(int *A, int N)
{
 A = new int [MAX];
 
 int i = 0 , j = 0;
 
 for (i = N - 1; i >= 0; --i)  
     {
      printf("\n\t\t\t\t - A [%d] : ",j);
      scanf("%d",&A[j]);
      j++;
     }
 return A;              
}

int kadane(int *A, int N, int maximo)
{
 maximo = 0;
 int max_temp = 0;
  
 for (int i = 0; i < N; i++)  
     {
      max_temp = A[i] + max_temp;
      
      if( max_temp < 0 )
          max_temp = 0;

      if( maximo < max_temp )
          maximo = max_temp;
     }
     
 return maximo;           
}

int main()
{


 int *A = NULL;
 int N ;
 int maximo;
 
 printf("\n\n\t Ingresar Longitud del Arreglo : ");
 scanf("%d",&N);
 
 A = ingresar( A , N );
 
 maximo = kadane( A , N , maximo);
 
 printf("\n\n\t\t\t\tMaximo = %d",maximo);

 return 0;
}

Código Informático

Algoritmo de Kadane [Codigo en C++]

1 comentarios: