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 del algoritmo 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.

Enlaces externos

• Wikilibros alberga el problema resuelto del subvector de suma máxima.

• Datos: Q6134997