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.
Frno-MAx-CRossING-SUBARRAY(A, low, mid, high)
1 left-sum = -oo
2sum = O
3 for i = mid downto low
4 sum = sum + A[í]
5 if sum > left-sum
6 left-sum = sum
7 max-left = i
8 right-sum = -oo
9 sum = O
10 forj =mui+ 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-/eft e max-right que demarcam um subarranjo máximo que cruza o ponto médio, juntamente com a soma /eft sum+right-sum dos valores no subarranjo A[max /eft.. max-right].

Answer

A) As linhas 1-7 acham um subarranjo maxImo da metade esquerda, A[/ow . . 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é /ow, de modo que todo subarranjo que ele considera é da forma A[i.. /ow].

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 /eft-sum, atualizaremos /eft-sum para a soma desse subarranjo na linha 6, e na linha 7 atualizaremos a variável max-/eft 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 índicej 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 Algoritmos de ordenação, busca e complexidade