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

Como resolver o problema da Subsequência de Soma Máxima em Java usando o Algorítmo de Kadane - Lista de Exercícios Resolvidos de Java

Quantidade de visualizações: 585 vezes

Pergunta/Tarefa:

O problema do Subvetor Contíguo de Soma Máxima, ou Subarray ou Subsequência de Soma Máxima é um dos algorítmos mais populares na programação dinâmica. Este problema envolve encontrar um subvetor, ou seja, um sub-array contíguo de maior soma possível. Por contíguo entendemos que os elementos da subsequência deverão estar consecutivos no vetor original.

O Algorítmo de Kadane, inventado por Jay Kadane em 1977, é um dos favoritos para a resolução deste problema, e deverá ser aplicado na resolução deste exercício.

Dado o vetor [-2, 1, -3, 4, -1, 2, 1, -5, 4], encontre a soma máxima da subsequência contígua. Não é exigido mostrar os elementos da sub-sequência, apenas o valor da soma máxima.

Sua saída deverá ser parecida com:

A soma maxima é: 6

Resposta/Solução:

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

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 inserir um nó no final de uma lista duplamente encadeada em Java - Escreva um programa Java que pede para o usuário - Desafio de Programação em Java

Um programa Java para praticar contas de soma (adição) com números aleatórios sorteados pelo computador - Desafio de Programação em Java

Como retornar o último elemento de um array em Java - Desafio de Programação em Java

Escreva um programa Java que pede para o usuário informar um número inteiro positivo de dois dígitos (Ex: 17) e mostre a soma de seus dígitos - Exercícios Resolvidos de Java

Percorrer todos os elementos de um array, exibir a soma dos valores positivos e a quantidade de valores negativos - Desafio de Programação em Java

Escreva um programa Java que leia e apresente um conjunto de números inteiros para uma matriz bidimensional 2 x 4 e apresente o valor e a posição - Exercícios Resolvidos de Java

Como desenhar um triângulo de números em Java usando laços - Exercícios Resolvidos de Java

Escreva um programa Java para encontrar o primeiro caractere não repetido em uma string - Versão usando laços - Desafio de Programação em Java

Ler três números inteiros e indicar se eles estão em ordem crescente ou decrescente - Desafio de Programação em Java

Escreva um programa em Java para ler, calcular e escrever a média aritmética entre dois números - Exercícios Resolvidos de Java

Uma função Java que recebe um valor inteiro e informa se o mesmo é um número primo - Exercício Resolvido de Java

Como resolver problemas de razão e proporção em Java - Em uma empresa, a razão entre o número de mulheres e o número - Exercícios Resolvidos de Java

Um programa que lê três números e os classifica e exibe em ordem crescente - Exercício Resolvido de Java

Como testar se um número é potência de três usando Java - Desafio de Programação em Java

Escreva um programa Java que mostre a data atual e a data que será daqui a 10 dias, ou seja, a data atual acrescida de 10 dias - Desafio de Programação em Java

Como ler o conteúdo de um arquivo texto e armazená-lo em uma variável string usando Java - Desafio de Programação em Java

Métodos - Um método estático que recebe um vetor de inteiros e o exibe - Desafio de Programação em Java

Uma loja está concedendo desconto de 20% para clientes do sexo feminino com idade entre 18 e 35 anos (ambas incluídas) - Desafio de Programação em Java

Numa promoção exclusiva para o Dia da Mulher, uma loja quer dar descontos para todos, mas especialmente para mulheres. Faça um programa - Desafio de Programação em Java

Laços - Faça um programa para calcular o valor das seguintes expressões - Desafio de Programação em Java

Exceções e Tratamentos de Erros - Exercícios Resolvidos 2 - Provocando e se recuperando de uma exceção java.lang.ArithmeticException: / (division) by zero - Desafio de Programação em Java

Usando o laço while para encontrar o MDC (Máximo Divisor Comum) de dois números - Desafio de Programação em Java

Internet, Rede e E-Mail - Exercício Resolvido 2 - Desafio de Programação em Java

Usando o laço for para exibir a tabela de caracteres ASCII de 1 até 127 - Exercício Resolvido de 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

Um método recursivo que calcula o MDC (máximo divisor comum) entre dois números inteiros - Desafio de Programação em Java

Escreva um programa Java console que solicite ao usuário que informe dois valores inteiros. Em seguida seu programa deverá efetuar a soma dos dois valores e exibí-la - Exercícios Resolvidos de Java

Como percorrer todos os elementos de um vetor de inteiros e exibir a soma de seus valores - Exercícios Resolvidos de Java

Como inverter a ordem dos elementos de um array usando apenas uma variável temporária - Desafio de Programação em Java

POO - Programação Orientada a Objetos - Exercício Resolvido 5 - A classe Dado (construtores, métodos, getters e setters e encapsulamento) - Desafio de Programação em Java

Veja mais Dicas e truques de Java

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

Exercícios Resolvidos de Java - Como inserir um nó no início de uma lista duplamente encadeada em Java - Escreva um programa Java que pede para o usuário

Java para iniciantes - Como usar a classe Console da linguagem Java

Exercício Resolvido de Java - Como calcular o restante de um salário após o pagamento de duas contas com juros

Efetuando conversões de decimal para binário usando o método toBinaryString()

Como usar a classe GregorianCalendar do Java em suas aplicações

Exercício Resolvido de Java - Como testar se um ano é bissexto em Java - Um programa que lê um ano com quatro dígitos e informa se ele é bissexto ou não

Exercícios Resolvidos de Java - Ler um número de três dígitos, separá-lo e invertê-lo, escrevendo o número lido e sua forma inversa

Escrevendo uma classe que extende a classe abstrata MouseAdapter

Como renomear um diretório em Java usando o método renameTo() da classe File - Arquivos e diretórios em Java

Dicas e truques de outras linguagens

Java - Exercício Resolvido de Java - Como percorrer todos os elementos de um vetor de inteiros e exibir a soma de seus valores

C - Exercícios Resolvidos de C - Como resolver problemas de razão e proporção em C - Em uma empresa, a razão entre o número de mulheres e o número

C++ - Como calcular a Energia Potencial Gravitacional de um corpo dado a sua massa e altura em C++

C# - Como retornar a coluna da célula selecionada em um DataGridView do C# Windows Forms

Python - Python para iniciantes - Como inserir uma determinada quantidade de espaços à direita de uma string

Java - Java Swing - Como alterar a cor de fundo dos títulos de uma JTable usando o método setBackground() da classe JTableHeader

C - Exercícios Resolvidos de C - Desafio do número ausente. Dado um vetor de números naturais 1..n, encontre o valor ausente

Python - Exercícios Resolvidos de Python - Como usar a Ordenação da Bolha em Python para ordenar os valores de um vetor em ordem crescente ou decrescente

C# - Tutorial C# para iniciantes - Como escrever seu primeiro método ou função em C#

C# - Como calcular a diferença de anos, meses ou dias entre duas datas em C# usando a função Subtract() da classe DateTime

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 resolver o problema da Subsequência de Soma Máxima em Java usando o Algorítmo de Kadane - 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