Question

O procedimento FIND-MAX-CROSSING-SUBARRAY, pela técnica de divisão e conquista, toma como entrada o arranjo A e os índices low, mid e high, e retorna uma tupla que contém os índices que demarcam um subarranjo máximo que cruza o ponto médio, juntamente com a soma dos valores em um subarranjo máximo.

Analise a estrutura a seguir:

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
1 left-sum = -∞
2 sum = 0
3 for i = mid downto low
4 sum = sum + A[i]
5 if sum > left-sum
6 left-sum = sum
7 max-left = i
8 right-sum = -∞
9 sum = 0
10 for j = mid + 1 to high
11 sum = sum + A[j]
12 if sum > right-sum
13 right-sum = sum
14 max-right = j
15 return (max-left, max-right, left-sum + right-sum)

Acerca das funções descritas acima, assinale a alternativa CORRETA.

Accepted Answer

E) A linha 15 retorna os índices max-left e max-right que demarcam um subarranjo máximo que cruza o ponto médio, juntamente com a soma left-sum+right-sum dos valores no subarranjo A[max-left . . max-right].

Answer

A) As linhas 1-7 acham um subarranjo máximo da metade esquerda, A[low . . mid]. Visto que esse subarranjo deve conter A[mid], o laço downto das linhas 3-7 inicia o índice i em mid e prossegue até low, de modo que todo subarranjo que ele considera é da forma A[i . . low].

Answer

B) As linhas 1-2 inicializam as variáveis sum, que contêm a maior soma encontrada até então, e left-sum, que contêm as somas das entradas em A[i . . mid].

Answer

C) Sempre que encontrarmos, na linha 5, um subarranjo A[i . . mid] com uma soma de valores menor do que left-sum, atualizaremos left-sum para a soma desse subarranjo na linha 6, e na linha 7 atualizaremos a variável max-left para registrar esse índice i.

Answer

D) As linhas 8-14 funcionam de modo análogo para a metade direita, A[mid+1 . . high]. Aqui, o laço for das linhas 10-14 inicia o índice j em mid+1 e prossegue até right-sum, de modo que todo subarranjo que ele considera é da forma A[mid + 1 . . i ].

Mais questões de Lógica de programação e algoritmos