- Fundamentos de ProgramaçãoAlgoritmosAnálise de Execução de Algoritmos
- Fundamentos de ProgramaçãoAlgoritmosDividir e Conquistar
- Fundamentos de ProgramaçãoPseudocódigo
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.