divide

Universidad de Granada
E.T.S. Ingeniería Informática

Departamento de Ciencias de la Computación e
Inteligencia Artificial

Teoría de Algoritmos
Divide y Vencerás

Curso 2005 – 2006Ingeniería Informática

1.

Objetivo

El objetivo de esta práctica es que el alumno analice, diseñe e implemente
un algoritmo basado en la técnica divide y vencerás para resolver el problema
deobtener la subsecuencia de suma máxima en un vector.
2.

Introducción

Dado un vector de números enteros V , con elementos V [i], i ∈ 1 . . . n
deseamos encontrar el valor de la expresión
jmax1≤i≤j≤n

V [k]
k=i

es decir, el subvector contiguo cuya suma sea máxima.
Por ejemplo, siendo
V = {31, −41, 59, 26, −53, 58, 97, −93, −23, 84}

el resultado sería 187, correspondiendo con lasuma de los valores
V [3] + V [4] + V [5] + V [6] + V [7]
2.1.

Algoritmos Básicos

Algoritmo 1: en una primera aproximación, intuitivamente podríamos
aplicar la siguiente idea para resolverel problema: para todo i, j con
j

1 ≤ i ≤ j ≤ n calculamos la suma

V [k] y nos quedamos con el valor
k=i

máximo encontrado. Claramente, este algoritmo es de orden cúbico.

Algoritmo 2: elalgoritmo previo puede transformarse a otro de orden
j

cuadrático teniendo en cuenta que la suma

V [k] puede obtenerse
k=i

j−1

aprovechando el cálculo previo de

V [k].
k=iAlgoritmo 3: otro algoritmo de orden cuadrático se puede obtener
utilizando un vector auxiliar A, que sirva para almacenar las sumas
parciales de manera que A[i] = V [1]+V [2]+. . .+V [i]. La construcciónde A es de orden lineal. Luego para calcular la sumatoria entre los
valores i, j de V , basta con hacer A[j] − A[i − 1]. (si quiero saber
cuanto gasté entre abril y septiembre, entonces al gastoacumulado
hasta septiembre debo restarle el gasto acumulado hasta marzo).
1

2.2.

Algoritmo Divide y Vencerás

Veamos ahora como se puede utilizar la técnica de Divide y Vencerás
para...