Subvector de suma máxima
![]() | Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «Subvector de suma máxima» – noticias · libros · académico · imágenes Este aviso fue puesto el 22 de marzo de 2016. |
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