Problema de sub-matriz máxima em C ++

O problema máximo de sub-matriz é o mesmo que o problema máximo de fatia. Este tutorial discute o problema com a codificação em C++. A questão é: qual é a soma máxima de qualquer sequência possível de números consecutivos dentro de uma matriz? Isso pode significar toda a matriz. Esse problema e sua solução em qualquer idioma são chamados de problema máximo de sub-matriz. A matriz pode ter possíveis números negativos.

A solução deve ser eficiente. Precisa ter a complexidade mais rápida. A partir de agora, o algoritmo mais rápido para a solução é conhecido na comunidade científica como o algoritmo de Kadane. Este artigo explica o algoritmo de Kadane com C++.

Exemplos de dados

Considere o seguinte vetor (Array):

vetor A = 5, -7, 3, 5, -2, 4, -1;

A fatia (sub -matriz) com a soma máxima é a sequência, 3, 5, -2, 4, que fornece uma soma de 10. Nenhuma outra sequência possível, mesmo toda a matriz, dará uma soma de até o valor de 10. Toda a matriz dá uma soma de 7, que não é a soma máxima.

Considere o seguinte vetor:

vetor B = -2, 1, -3, 4, -1, 2, 1, -5, 4;

A fatia (sub-matriz) com a soma máxima é a sequência, 4, −1, 2, 1, que fornece uma soma de 6. Observe que pode haver números negativos dentro da sub-matriz para a soma máxima.

Considere o seguinte vetor:

vetor C = 3, 2, -6, 4, 0;

A fatia (sub-matriz) com a soma máxima é a sequência, 3, 2, que fornece uma soma de 5.

Considere o seguinte vetor:

vetor D = 3, 2, 6, -1, 4, 5, -1, 2;

A sub -matriz com a soma máxima é a sequência, 3, 2, 6, -1, 4, 5, -1, 2, que dá uma soma de 20. É toda a matriz.

Considere o seguinte vetor:

vetor E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22;

Existem dois sub-maiores com somas máximas, aqui. A soma mais alta é a que é considerada como solução (resposta) para o problema máximo de sub-matriz. Os sub -maiores são: 5, 7 com uma soma de 12 e 6, 5, 10, -5, 15, 4 com uma soma de 35. Claro, a fatia com a soma de 35, é a resposta.

Considere o seguinte vetor:

vetor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2;

Existem dois sub-maiores com somas máximas. A soma mais alta é a que é considerada como solução para o problema máximo de sub-matéria. Os sub-maiores são: 10, 15, 9 com uma soma de 34 e 4, 6, 3, 2, 8, 3 com uma soma de 26. Obviamente, a fatia com a soma de 34 é a resposta, porque o problema é procurar a sub-matriz com a soma mais alta e não a sub-matriz com a soma superior.

Desenvolvendo o algoritmo de Kadane

As informações nesta seção do tutorial não são o trabalho original de Kadane. É a maneira da própria maneira do autor de ensinar o algoritmo de Kadane. Um dos vetores acima, com seus totais em execução, está nesta tabela:

O total em execução para um índice é a soma de todos os valores anteriores, incluindo a do índice. Existem duas sequências com somas máximas aqui. Eles são 5, 7, que fornecem uma soma de 12 e 6, 5, 10, -5, 15, 4, que fornece uma soma de 35. A sequência que dá uma soma de 35 é o que é desejado.

Observe que, para os totais em execução, existem dois picos que são os valores, 12 e 27. Esses picos correspondem aos últimos índices das duas seqüências.

Portanto, a idéia do algoritmo de Kadane é estar fazendo o total em execução enquanto compara as somas máximas à medida que são encontradas, passando da esquerda para a direita na matriz dada.

Outro vetor de cima, com seus totais em execução, está nesta tabela:

Existem duas sequências com somas máximas. Eles são 10, 15, 9, que fornecem uma soma de 34; e 4, 6, 3, 2, 8, 3, que dá uma soma de 26. A sequência que dá a soma de 34, é o que é desejado.

Observe que, para os totais em execução, existem dois picos que são os valores, 30 e 13. Esses picos correspondem aos últimos índices das duas seqüências.

Novamente, a idéia do algoritmo de Kadane é estar fazendo o total em execução enquanto compara as somas máximas à medida que são encontradas, passando da esquerda para a direita na matriz dada.

Código pelo algoritmo de Kadane em C++

O código fornecido nesta seção do artigo não é necessariamente o que Kadane usou. No entanto, é por seu algoritmo. O programa como muitos outros programas C ++ começaria com:

#incluir
#incluir

usando namespace std;

Há inclusão da biblioteca iostream, responsável pela entrada e saída. O espaço para nome padrão é usado.

A idéia do algoritmo de Kadane é ter o total em execução enquanto compara as somas máximas à medida que são encontradas, passando da esquerda para a direita na matriz dada. A função para o algoritmo é:

int maxsunarray (vetor &A)
int n = a.tamanho();
int maxsum = a [0];
int runtotal = a [0];
para (int i = 1; i < N; i++)
int tempRuntotal = runtotal + a [i]; // pode ser menor que um [i]
if (a [i]> temproTotal)
RUNTOTAL = A [i]; // Caso um [i] seja maior do que o total de execução
outro
RUNTOTAL = TEMPRUNTOTAL;
if (runtotal> maxsum) // comparando todas as somas máximas
maxsum = runtotal;

retornar maxsum;

O tamanho, n da matriz dada (vetor) é determinada. A variável, Maxsum é uma das somas máximas possíveis. Uma matriz tem pelo menos uma soma máxima. A variável, Runtotal representa o total em execução em cada índice. Ambos são inicializados com o primeiro valor da matriz. Nesse algoritmo, se o próximo valor na matriz for maior que o total em execução, esse próximo valor se tornará o novo total em execução.

Há um alvo principal. A varredura começa em 1 e não zero devido à inicialização das variáveis, maxsum e runtotal para um [0] que o primeiro elemento da matriz dada.

No loop for, a primeira declaração determina um total temporário de execução, adicionando o valor atual à soma acumulada de todos os valores anteriores.

Em seguida, há um if/else construto. Se o valor atual é maior que o total em execução até agora, esse valor único se tornará o total em execução. Isso é útil, especialmente se todos os valores na matriz dada forem negativos. Nesse caso, o maior valor negativo por si só se tornará o valor máximo (a resposta). Se o valor atual por si só não for maior que o total temporário em execução até agora, o total em execução se tornará o total anterior de execução mais o valor atual, - esta é a parte da parte do if/else construto.

O último segmento de código no loop for escolhido entre qualquer soma máxima anterior para uma sequência anterior (sub-matriz) e qualquer soma máxima atual para uma sequência atual. O valor mais alto é, portanto, escolhido. Pode haver mais de uma soma máxima de sub-matriz. Observe que o total em execução aumentaria e diminuiria, pois a matriz é escaneada da esquerda para a direita. Cai quando atende a valores negativos.

A soma final de sub-matriz máxima escolhida é devolvida após o loop for.

O conteúdo de uma função principal C ++ adequada, para a função de algoritmo de Kadane é:

vetor A = 5, -7, 3, 5, -2, 4, -1; // 3, 5, -2, 4 -> 10
int ret1 = maxsunarray (a);
cout << ret1 << endl;
vetor B = -2, 1, -3, 4, -1, 2, 1, -5, 4; // 4, -1, 2, 1 -> 6
int ret2 = maxsunarray (b);
cout << ret2 << endl;
vetor C = 3, 2, -6, 4, 0; // 3, 2 -> 5
int ret3 = maxsunarray (c);
cout << ret3 << endl;
vetor D = 3, 2, 6, -1, 4, 5, -1, 2; // 3, 2, 6, -1, 4, 5, -1, 2 -> 5
int ret4 = maxsunarray (d);
cout << ret4 << endl;
vetor E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22; // 6, 5, 10, -5, 15, 4 -> 35
int ret5 = maxsunarray (e);
cout << ret5 << endl;
vetor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2; // 10, 15, 9-> 34
int ret6 = maxsunarray (f);
cout << ret6 << endl;

Com isso, a saída será:

10

6

5

20

35

34

Cada resposta de linha aqui corresponde a uma determinada matriz, em ordem.

Conclusão

A complexidade do tempo para o algoritmo de Kadane é O (n), onde n é o número de elementos na matriz dada. Desta vez, a complexidade é a mais rápida para o problema máximo de sub-matriz. Existem outros algoritmos que são mais lentos. A idéia do algoritmo de Kadane é estar fazendo o total em execução, enquanto compara as somas máximas à medida que são encontradas, passando da esquerda para a direita na matriz dada. Se o valor atual é maior que o total em execução até agora, esse valor único se tornará o novo total em execução. Caso contrário, o novo total em execução é o total anterior e o elemento atual, conforme previsto, pois a matriz dada é digitalizada.

Pode haver mais de uma soma máxima, para diferentes sub-maiores de teatro. A soma máxima mais alta, para todos os sub-maiores possíveis, é escolhida.

Quais são os índices limitantes para o alcance da soma máxima escolhida? - Isso é discussão para algum outro momento!

Chrys