Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
O procedimento FIND-MAX-CROSSING-SUBARRAY, pela técnica de...
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[i]
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.
A
As linhas 1-7 acham um subarranjo maxImo 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].
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].
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.
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].
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].