- Subvector de suma máxima
-
El problema del subvector de suma máxima consiste en encontrar un subvector de una determinada longitud m cuya suma sea máxima dentro de un vector de longitud n, con m≤n.
Este problema se puede resolver aplicando la técnica de divide y vencerás, formando problemas cada vez más pequeños hasta alcanzar un caso base y posteriormente combinando las soluciones obtenidas. En concreto, la forma de aplicar el método algorítmico citado consiste en obtener los segmentos de suma máxima correspondientes a las mitades izquierda y derecha del vector y a la parte central para, una vez calculados, elegir el máximo de los tres. El algoritmo tiene un coste lineal respecto al tiempo.
Enlace externo
- Wikilibros alberga el problema resuelto del subvector de suma máxima.
Categoría:- Problemas computacionales
Wikimedia foundation. 2010.