max_pair.py

"""
retorno:
  (array[j] - array[j], i, j) tais que
  -   array[j] - array[i] é máximo
  -   0 <= i <= j <= n; n = len(array)
"""
def max_pair(array):
    # len(array) = n
    # caso base: n = 2
	if len(array) == 2:
		return (array[1] - array[0], 0, 1)

    # maximum = array[j] - array[i]
    # array[0:-1] = array[0 .. n-1]
	(maximum, i, j) = max_pair(array[0:-1])

	for (index, element) in enumerate(array[0:-1]):
        # array[-1] é o último elemento do array
		if array[-1] - element > maximum:
			maximum = array[-1] - element
			i = index
			j = len(array) - 1

	return (maximum, i, j)

"""
retorno:
  (array[j] - array[j], i, j, m) tais que
  -   array[j] - array[i] é máximo
  -   0 <= i <= j <= n; n = len(array)
  -   m é o índice do menor elemento do array
"""
def max_pair2(array):
	if len(array) == 2:
		m = 0 if array[0] < array[1] else 1
		return (array[1] - array[0], 0, 1, m)

	(maximum, i, j, m) = max_pair2(array[0:-1])

	if array[-1] - array[m] > maximum:
		maximum = array[-1] - array[m]
		i = m
		j = len(array) - 1

    # manutenção do índice do menor elemento
	if array[-1] < array[m]:
		m = len(array) - 1

	return (maximum, i, j, m)