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: 441 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.

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package estudos;

import java.util.Arrays;

public class Estudos{
  public static void main(String args[]){
    // vamos criar um vetor com 8 elementos
    int valores[] = {-7, 1, 3, 11, 5, -4, 9, 2};
    // vamos mostrar os valores do array
    System.out.println("O conteúdo do array é: " +
      Arrays.toString(valores));
    
    // definimos o tamanho da subsequencia
    int k = 3;
    // e o tamanho do vetor
    int n = valores.length;
 
    // e chamamos a função que retorna a soma máxima
    int soma_maxima = soma_maxima_subarray_k(valores, n, k);
    // finalmente mostramos o resultado
    System.out.println("A soma máxima é: " + soma_maxima);
  }
  
  // método que recebe um vetor v e um número inteiro
  // k e retorna a maior soma que pode ser obtida por
  // uma subsequencia contígua de tamanho k
  static int soma_maxima_subarray_k(int arr[], int n, int k){
    // o primeiro passo é declarar a soma
    // máxima como 0
    int soma_maxima = 0;
    
    // agora percorremos os elementos do vetor, começando
    // no primeiro e indo até o elemento indicado pelo
    // tamanho do array menos o k
    for (int i = 0; i <= n - k; i++) {
      // criamos uma variável temporário com valor 0
      int soma_temp = 0;
      
      // fazemos a soma dos elementos começando no
      // índice i atual e percorrendo
      // a quantidade de elementos k
      for (int j = i; j < i + k; j++) {
        // adicionamos o valor do elemento no índice j
        // à soma temporária
        soma_temp += arr[j];
      }
      
      // a soma temporária é maior que a soma
      // que já temos?
      if (soma_temp > soma_maxima) {
        // a nova soma é a soma temporária
        soma_maxima = soma_temp;
      }
    }
 
    // retorna a soma máxima
    return soma_maxima;
  }
}


Link para compartilhar na Internet ou com seus amigos:

Java ::: Desafios e Lista de Exercícios Resolvidos ::: Java Básico

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

Quantidade de visualizações: 4762 vezes
Pergunta/Tarefa:

Cintia acaba de receber seu salário mas precisa pagar duas contas atrasadas. Por causa do atraso, ela deverá pagar multa de 2% sobre cada conta. Faça um programa que leia o valor do salário e das duas contas e que calcule e mostre quanto restará do salário de Cintia.

Sua saída deverá ser parecida com:

Informe o salário: 1350
Valor da primeira conta: 140
Valor da segunda conta: 300

Total das contas sem juros: 440.0
Total dos juros: 8.8
Total das contas com juros: 448.8
Sobra do salário: 901.2
Resposta/Solução:

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

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package estudos;

import java.util.Scanner;

public class Estudos {
  public static void main(String[] args) {
    // para ler a entrada do usuário
    Scanner entrada = new Scanner(System.in);  
    
    // vamos pedir que o usuário informe o valor do salário e das duas contas
    System.out.print("Informe o salário: ");
    double salario = Double.parseDouble(entrada.nextLine());
    System.out.print("Valor da primeira conta: ");
    double conta1 = Double.parseDouble(entrada.nextLine());
    System.out.print("Valor da segunda conta: ");
    double conta2 = Double.parseDouble(entrada.nextLine());
    
    // total a ser pago nas duas contas sem os juros
    double totalContas = conta1 + conta2;
    // calcula os juros
    double totalJuros = totalContas * 0.02;
    // total a ser pago com juros
    double totalContasComJuros = totalContas + totalJuros;
    // sobra do salário
    double sobraSalario = salario - totalContasComJuros;
    
    // mostra os resultados
    System.out.println("\nTotal das contas sem juros: " + totalContas);
    System.out.println("Total dos juros: " + totalJuros);
    System.out.println("Total das contas com juros: " + totalContasComJuros);
    System.out.println("Sobra do salário: " + sobraSalario);
    
    System.out.println("\n");
  }
}



Java ::: Dicas & Truques ::: Imagens e Processamento de Imagens

Como carregar uma imagem em um BufferedImage do Java usando o método read() da classe ImageIO

Quantidade de visualizações: 12140 vezes
O método read() da classe ImageIO possui várias assinaturas. Entre elas há uma que aceita um objeto File representando o caminho e nome da imagem a ser carregada. Este método retorna um BufferedImage e atira uma exceção IOException se a imagem não puder ser carregada.

O exemplo abaixo mostra como carregar uma imagem JPG em um BufferedImage usando ImageIO.read():

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

import java.awt.*;
import java.io.*;
import java.awt.image.*;
import java.awt.event.*;
import javax.swing.*;
import javax.imageio.*;

public class Estudos extends JFrame{
  private BufferedImage imagem;
  
  public Estudos() {
    super("Estudos Java");
    
    Container c = getContentPane();
    c.setLayout(new FlowLayout());
	
    JButton btn = new JButton("Carregar Imagem");
    btn.addActionListener(
      new ActionListener(){
        public void actionPerformed(ActionEvent e){
          imagem = null;
          
          try{
            imagem = ImageIO.read(
              new File("imagens/fundo.jpg"));
          }
          catch(IOException exc){
            JOptionPane.showMessageDialog(null, 
              "Erro ao carregar a imagem: " + 
              exc.getMessage());
          }

          if(imagem != null)
            JOptionPane.showMessageDialog(null, 
              "Imagem carregada com sucesso.");
        }
      }
    );

    c.add(btn);
    	
    setSize(400, 300);
    setVisible(true);
  }
  
  public static void main(String args[]){
    Estudos app = new Estudos();
    app.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }
}



Java ::: Dicas & Truques ::: Arquivos e Diretórios

Como criar um arquivo em Java usando o método createNewFile() da classe File

Quantidade de visualizações: 19 vezes
Nesta dica mostrarei como é possível usar o método createNewFile() da clase File, do pacote java.io, para criar um novo arquivo. Note que estou usando um bloco try...catch para tratar os possíveis erros decorrentes desta operação.

Veja o código completo para o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package arquivodecodigos;

import java.io.*;
 
public class Estudos{
  public static void main(String[] args){
    try{
      File arquivo = new File("c:\\estudos_java\\osmar.txt");
         
      // Cria o arquivo se este não existe ainda
      boolean ok = arquivo.createNewFile();
         
      // o arquivo foi criado com sucesso?
      if(ok){
        System.out.println("Arquivo criado com sucesso.");
      } 
      else{
        System.out.println("Nao foi possivel criar o arquivo.");
      }
    }
    catch(IOException e){
      System.out.println("Erro: " + e.toString());
    }
  }
}

Ao executar este código nós teremos o seguinte resultado:

Arquivo criado com sucesso.


Desafios, Exercícios e Algoritmos Resolvidos de Java

Veja mais Dicas e truques de Java

Dicas e truques de outras linguagens

Códigos Fonte

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento
Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidadesControle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades
Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais

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



© 2025 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 68 usuários muito felizes estudando em nosso site.