Você está aqui: Java ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes)

Como encontrar a soma máxima em uma subsequência de tamanho k em Java - Programação Dinâmica em Java - Lista de Exercícios Resolvidos de Java

Quantidade de visualizações: 509 vezes

Pergunta/Tarefa:

Este desafio, presente em quase todos os livros de programação dinâmica em Java, envolve encontrar a soma máxima em um subarray contíguo, ou seja, de elementos consecutivos, obedecendo a um tamanho k.

O tamanho k determina a quantidade de elementos que a subsequencia pode ter. É possível ter mais de um subarray de tamanho k que contenha a soma máxima, mas o exercício pede para retornar apenas a soma máxima. Em outras abordagens do site eu mostro como retornar a quantidade de subarrays e até mesmo os índices de início e término de cada uma dessas subsequencias.

Assim, dado o vetor v[] de números inteiros [-7, 1, 3, 11, 5, -4, 9, 2], encontre a maior soma que pode ser obtida por uma sequencia contígua de 3 elementos.

Sua saída deverá ser parecida com:

O conteúdo do array é: [-7, 1, 3, 11, 5, -4, 9, 2]
A soma máxima é: 19

Embora o exercício não peça para mostrar a sub-sequência com a maior soma, você pode fazer o teste de mesa no algorítmo e verificar que o sub-array de 3 elementos que contém a soma máxima é [3, 11, 5]

Resposta/Solução:

Veja a resolução comentada deste exercício usando Java:

Atenção: Existem muitos algorítmos refinados para uma solução mais eficiente deste problema. Aqui eu apresento a solução usando força-bruta. Essa é a forma mais ineficiente e que consome mais tempo e recursos da máquina. No entanto, esta é também a forma mais fácil de entender o algorítmo aplicado.

Este trecho de código ou resolução de exercício faz parte do Super Pack 12.000 Dicas e Truques de Programação e 1.500 Exercícios Resolvidos em Java, Python, VisuAlg, Portugol, Delphi, C#, C, C++, VB.NET, Golang, Pascal, Ruby, PHP, e várias outras linguagens.

Aprenda a programar resolvendo problemas do mundo real. Tudo em português, com comentários em português.

Quero Ser Apoiador(a)

Link para compartilhar na Internet ou com seus amigos:

Mais Desafios de Programação e Exercícios e Algoritmos Resolvidos de Java

Como encontrar o maior valor em um ArrayList de inteiros usando o laço for - Exercício Resolvido de Java

Escreva um programa Java que pede para o usuário informar o seu nome e seu sobrenome, cada um em variáveis separadas. Faça a validação - Desafio de Programação em Java

Como encontrar o par de elementos em um vetor que, somados, resulte no número informado - Solução usando força-bruta - Desafio de Programação em Java

Declarar e construir um vetor de inteiros e usar um laço for para inicializar seus elementos com os valores de 1 até 10 em Java - Desafio de Programação em Java

Algorítmos Resolvidos de Java - A classe Retangulo (construtores, getters e setters, encapsulamento e static) - Desafio de Programação em Java

Escreva um programa que leia o ano de nascimento de um rapaz e mostre a sua situação em relação ao alistamento militar - Desafio de Programação em Java

Programa de cálculo de médias de alunos. Escrever um programa Java que cadastre o nome, a matrícula e duas notas de vários alunos - Desafio de Programação em Java

Como aplicar a Fórmula da Vazão pelo Método Racional em Java - De acordo com o método racional, a vazão máxima a ser considerada - Desafio de Programação em Java

Crie uma classe Esfera contendo um atributo de instância chamado diametro, do tipo double. Defina um construtor público que receberá o valor do diâmetro - Exercícios Resolvidos de Java

Como calcular lucro mensal de uma empresa em Java - O lucro de uma empresa é dado por L(x) = 10x - 5000, onde x é a quantidade - Exercícios Resolvidos de Java

Listando arquivos e diretórios em um diretório informado pelo usuário - Exercícios Resolvidos de Java

Como forçar o usuário a informar dois inteiros válidos antes de efetuar sua soma - Exceções e Tratamentos de Erros em Java - Exercício Resolvido de Java

Como calcular o comprimento de um segmento de reta usando Java - Exercícios Resolvidos de Java

Uma pousada estipulou o preço para a sua diária em R$ 30,00 e mais uma taxa de serviços diários de - Desafio de Programação em Java

Problema do cálculo e consulta do IMC de uma pessoa. Escrever um programa que cadastre o nome, a altura, o peso, o CPF e sexo de algumas pessoas - Desafio de Programação em Java

Exercícios Resolvidos de Java - Contando de 1 até 20 e formatando a saída usando System.out.printf() - Desafio de Programação em Java

Um método Java chamado calcular(int a, int b) que recebe duas variáveis do tipo int e multiplica um valor pelo outro. Em seguida - Exercício Resolvido de Java

Escreva um algoritmo Java que leia o nome de um vendedor, o seu salário fixo e o total de vendas efetuadas por ele no mês - Desafio de Programação em Java

Usando laços for aninhados para desenhar uma pirâmide de números em Java (com o usuário informando a quantidade de linhas) - Desafio de Programação em Java

Como inserir no final de uma lista ligada em Java - Escreva um programa Java que pede para o usuário informar vários - Desafio de Programação em Java

Elabore um programa Java que solicita e armazena 3 notas de 5 alunos em uma matriz 5x3, ou seja, 5 linhas e 3 colunas. Por fim - Desafio de Programação em Java

Matrizes - Exercícios Resolvidos 13 - Declarar e construir uma matriz de 10 int, solicitar ao usuário que informe os valores dos elementos e mostrar os índices do maior e do menor elemento - Desafio de Programação em Java

Como testar se um retângulo cabe dentro de um círculo usando Java - Exercício Resolvido de Java

Escreva um programa Java que pede para o usuário informar o salário de uma pessoa, o valor de um empréstimo e a quantidade de prestações - Desafio de Programação em Java

Faça um algoritmo que leia a nota de 10 alunos de uma turma e guarde-as em um vetor. No final, mostre - Exercício Resolvido de Java

Como ler e gravar arquivos texto com campos de tamanho fixo em Java - Nomes e notas de alunos aprovados e reprovados - Exercícios Resolvidos de Java

Como ler o conteúdo de um arquivo uma linha de cada vez usando Java - Desafio de Programação em Java

Um método recursivo que recebe uma String e retorna a quantidade de letras maiúsculas encontradas - Exercícios Resolvidos de Java

Escreva um programa Java para ler as notas n1 e n2 de um aluno e calcule a sua média aritmética - Desafio de Programação em Java

Como converter minutos em segundos em Java usando uma função - Desafio de Programação em Java

Veja mais Dicas e truques de Java

Obter uma lista dos nomes dos formatos que podem ser escritos pelas classes da versão atual do Java

Boleto Bancário Java - Como montar o campo livre do código de barras juntamente com o seu dígito verificador (Módulo 11) - Boleto Caixa Econômica

Java para iniciantes - Como substituir caracteres em uma string usando o método replace() da classe String

Exercícios Resolvidos de Java - Como converter decimal em binário em Java usando o laço while

Exercícios Resolvidos de Java - Como testar se uma matriz é uma Matriz Triangular Superior em Java

Usando GridBagConstraints.gridheight para definir a quantidade de células em uma coluna que um determinado componente ocupará

Como remover espaços em excesso de uma string usando expressões regulares em Java

Exercícios e Algorítmos Resolvidos de Java - Somando os elementos da diagonal principal de uma matriz

Java Swing - Como obter o valor selecionado em um JList usando o método getSelectedValue()

Como obter o índice do item selecionado em uma JList

Dicas e truques de outras linguagens

C - Como somar os elementos da diagonal principal de uma matriz em C

PHP - Como construir uma data usando a função mktime() do PHP

Java - Como converter Centímetros Cúbicos em Metros Cúbicos em Java - Java para Física e Engenharia

Java - Java Swing - Como usar a classe JSplitPane para dividir o espaço ocupado pelos componentes de suas aplicações Java Swing

Java - Exercício Resolvido de Java - Como simplificar frações em Java

Python - Exercícios Resolvidos de Python - Como calcular o peso de uma pessoa na Lua usando Python

Python - Python para iniciantes - Como usar o tipo de dados list da linguagem Python

Java - Exercício Resolvido de Java - Como calcular o Índice de Massa Corporal em Java - Como calcular IMC em Java

C++ - Como retornar uma referência ao último elemento de um vector C++ usando a função back()

Java - Exercícios Resolvidos de Java - Escreva um programa Java que leia duas notas obtidas por um aluno na disciplina de Algoritmos e Programação de Computadores, o número de aulas ministradas

E-Books em PDF

E-Book 350 Exercícios Resolvidos de Java - PDF com 500 páginas

Domine lógica de programação e a linguagem Java com o nosso E-Book 350 Exercícios Exercícios de Java, para você estudar onde e quando quiser.

Este e-book contém exercícios resolvidos abrangendo os tópicos: Java básico, matemática e estatística, programação dinâmica, strings e caracteres, entrada e saída, estruturas condicionais, vetores e matrizes, funções, laços, recursividade, internet, arquivos e diretórios, programação orientada a objetos e muito mais.

Ver Conteúdo do E-book

E-Book 650 Dicas, Truques e Exercícios Resolvidos de Python - PDF com 1.200 páginas

Domine lógica de programação e a linguagem Python com o nosso E-Book 650 Dicas, Truques e Exercícios Exercícios de Python, para você estudar onde e quando quiser.

Este e-book contém dicas, truques e exercícios resolvidos abrangendo os tópicos: Python básico, matemática e estatística, banco de dados, programação dinâmica, strings e caracteres, entrada e saída, estruturas condicionais, vetores e matrizes, funções, laços, recursividade, internet, arquivos e diretórios, programação orientada a objetos e muito mais.

Ver Conteúdo do E-book

Linguagens Mais Populares

1º lugar: Java
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: C
6º lugar: Delphi
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby

Você está aqui: Java ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes)

Como encontrar a soma máxima em uma subsequência de tamanho k em Java - Programação Dinâmica em Java - Lista de Exercícios Resolvidos de Java

Questões de Concurso para Engenharia Civil

Exercícios Resolvidos

Bancos de Dados

Questões de Concurso

Frameworks

Projetos e Códigos Fonte

Especializações

Calculadoras

Ferramentas

Todas as Linguagens, Frameworks, Biliotecas e Bancos de Dados

Compre pelo WhatsApp: +55 (062) 98553-6711

E-Book 350 Exercícios Resolvidos de Java - Com comentários em Português

PDF COM 500 PÁGINAS

Apenas R$ 19,90