Questão de TI - Desenvolvimento de Sistemas — Outros Tópicos de Desenvolvimento de Sistemas — Legalle 2023
TI - Desenvolvimento de SistemasOutros Tópicos de Desenvolvimento de Sistemas
- Código
- qa541834
- Banca
- Legalle
- Órgão
- DPE PA
- Ano
- 2023
- Cargo
- AnaDP ( )
O procedimento FIND-MAX-CROSSINGSUBARRAY, pela técnica de divisão e conquista, toma como entrada o arranjo A e os índices low, mide high, e retorna uma tupla que contém os indices 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:
Acerca das funções descritas acima, assinale a alternativa CORRETA.
- AAs linhas 1-7 acham um subarranjo máximo da metade esquerda, Aflow . . 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].
- BAs linhas 1-2 inicialzam 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].
- CSempre 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.
- DAs 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]
- EA 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 leftsum+ right-sum dos valores no subarranjo A[maxleft. . max-right].