Exercícios Práticos de Algoritmo Guloso

Problema 455: Distribuição de Biscoitos

A abordagem gulosa envolve ordenar as necessidades das crianças e os tamanhos dos biscoitos, e depois alocar o maior biscotio disponível para a criança com maior necessidade que ele possa satsifazer.

class Solucao {
public:
    int encontrarCriancasContentes(vector<int>& apetites, vector<int>& biscoitos) {
        sort(apetites.begin(), apetites.end());
        sort(biscoitos.begin(), biscoitos.end());
        int total = 0, idxBiscoito = biscoitos.size() - 1;
        for (int i = apetites.size() - 1; i >= 0; i--) {
            if (idxBiscoito >= 0 && biscoitos[idxBiscoito] >= apetites[i]) {
                total++;
                idxBiscoito--;
            }
        }
        return total;
    }
};

Problema 376: Sequência Oscilante Máxima

Para calcular o comprimento máximo de uma subsequência oscilante, mantemos um registro da diferença anterior e contamos as mudanças de direção.

class Solucao {
public:
    int comprimentoMaximoOscilante(vector<int>& numeros) {
        int resultado = 1;
        int direcaoAnterior = 0;
        for (size_t i = 1; i < numeros.size(); i++) {
            int diferenca = numeros[i] - numeros[i-1];
            if (diferenca > 0 && direcaoAnterior <= 0) {
                resultado++;
                direcaoAnterior = 1;
            } else if (diferenca < 0 && direcaoAnterior >= 0) {
                resultado++;
                direcaoAnterior = -1;
            }
        }
        return resultado;
    }
};

Problema 53: Soma Máxima de Subarray

A solução ótima usa o método de soma prefixada para calcular a soma máxima de subarray contínuo em tempo linear.

class Solucao {
public:
    int somaMaximaSubarray(vector<int>& numeros) {
        long long somaAtual = 0, minPrefixo = 0, melhorSoma = LLONG_MIN;
        for (int valor : numeros) {
            somaAtual += valor;
            melhorSoma = max(melhorSoma, somaAtual - minPrefixo);
            minPrefixo = min(minPrefixo, somaAtual);
        }
        return static_cast<int>(melhorSoma);
    }
};

Análise Detalhada da Abordgaem com Soma Prefixada

Vamos decompor a lógica do código acima:

• somaAtual: Acumula a soma prefixada até o índice corrente, representando S[j].
• minPrefixo: Armazena o valor mínimo das somas prefixadas encontradas até o índice anterior, inicializado como 0 para permitir subarrays iniciando do início.
• melhorSoma: Registra a maior soma de subarray vista até o momento.

A relação fundamental é que a soma de qualquer subarray (i, j] é S[j] - S[i]. Para maximizar isso para um j fixo, S[i] deve ser o menor possível, o que é rastreado por minPrefixo.

A ordem de operação é crucial:

1. Primeiro, calculamos somaAtual - minPrefixo usando o minPrefixo anterior, garantindo que consideramos subarrays não vazios.
2. Depois, atualizamos minPrefixo com o valor atual de somaAtual para uso nas iterações seguintes.

Isso mantém um invariante: após processar o índice j, minPrefixo contém min_{i≤j} S[i], e melhorSoma reflete a soma máxima até j.

Exemplo Passo a Passo

Para a lista nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], a soma máxima é 6, correspondendo ao subarray [4, -1, 2, 1].

No passo 6, melhorSoma torna-se 6, derivado de S[6] - minPrefixo = 2 - (-4), que mapeia para o subarray de índices 3 a 6.

Relação com o Algoritmo de Kadane

Ambos os métodos são equivalentes: Kadane maximiza a soma terminando em cada índice, enquanto a abordagem prefixada maximiza S[j] - min_{iObservações: Use tipos de dados maiores para evitar overflow, e note que o problema foca em subarrays contínuos, não subsequências.