Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n)…

Questão

Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a maior soma de k elementos contíguos usando repetições simples e aninhadas de forma eficiente. Inclua inicialização de variáveis e estruturas de loop.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo (janela deslizante): se n = 0 ou k > n então retornar erro soma := 0 para i de 1 até k faça soma := soma + A[i] fim para max := soma para i de k+1 até n faça soma := soma + A[i] - A[i-k] se soma > max então max := soma fim se fim para retornar max Complexidade O(n); usa uma variável de acumulação e um loop simples após inicialização.

Explicação

O algoritmo utiliza a técnica da janela deslizante para calcular a soma de k elementos contíguos de forma eficiente, evitando a necessidade de recalcular a soma de cada subvetor repetidamente. Ao inicializar a soma com os primeiros k elementos e, em seguida, ajustar essa soma ao adicionar o próximo elemento e subtrair o que saiu da janela, o algoritmo mantém a complexidade em O(n). Essa abordagem garante que todos os elementos sejam processados uma única vez, resultando em um desempenho otimizado.

Raio-X da questão

Questões parecidas com resolução

• Proponha um algoritmo em pseudocódigo que, dada uma lista A de n inteiros e um inteiro k>0, determine o comprimento do…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros, encontre o comprimento do maior subvetor…
• Projete um algoritmo em pseudocódigo que, dada uma lista A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a lista…
• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…
• Descreva um algoritmo em pseudocódigo que, dada uma matriz quadrada A[n][n] de inteiros e um inteiro k>0, percorra os…
• Projete um algoritmo in-place, em pseudocódigo, que receba um vetor A de n números distintos e um inteiro k (1 = k = n)…

Todas as questões de Programação - Algoritmos clássicos