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
[editar]
Wikilibros alberga el problema resuelto del subvector de suma máxima.
| Control de autoridades |
|
|---|
Datos: Q6134997