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 um array? Isso pode significar toda a matriz. Este problema e sua solução em qualquer idioma é chamado de Problema de Sub-matriz Máxima. A matriz pode ter possíveis números negativos.
A solução tem que ser eficiente. Ele precisa ter a complexidade de tempo mais rápida. A partir de agora, o algoritmo mais rápido para a solução é conhecido na comunidade científica como Algoritmo de Kadane. Este artigo explica o algoritmo de Kadane com C++.
Exemplos de dados
Considere o seguinte vetor (array):
vetor < int > A = { 5 , - 7 , 3 , 5 , - dois , 4 , - 1 } ;
A fatia (sub-array) com a soma máxima é a sequência, {3, 5, -2, 4}, que dá uma soma de 10. Nenhuma outra sequência possível, mesmo o array inteiro, dará uma soma de até o valor de 10. A matriz inteira dá uma soma de 7, que não é a soma máxima.
Considere o seguinte vetor:
vetor < int > B = { - dois , 1 , - 3 , 4 , - 1 , dois , 1 , - 5 , 4 } ;
A fatia (sub-array) com a soma máxima é a sequência, {4, −1, 2, 1} que dá uma soma de 6. Observe que pode haver números negativos dentro do sub-array para a soma máxima.
Considere o seguinte vetor:
vetor < int > C = { 3 , dois , - 6 , 4 , 0 } ;
A fatia (sub-array) com a soma máxima é a sequência, {3, 2} que dá uma soma de 5.
Considere o seguinte vetor:
vetor < int > D = { 3 , dois , 6 , - 1 , 4 , 5 , - 1 , dois } ;
O sub-array com a soma máxima é a sequência, {3, 2, 6, -1, 4, 5, -1, 2} que dá uma soma de 20. É o array inteiro.
Considere o seguinte vetor:
vetor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , quinze , 4 , - 8 , - quinze , - 22 } ;
Existem dois sub-matrizes com somas máximas, aqui. A maior soma é aquela que é considerada como solução (resposta) para o problema da submatriz máxima. As sub-matrizes são: {5, 7} com uma soma de 12 e {6, 5, 10, -5, 15, 4} com uma soma de 35. Obviamente, a fatia com a soma de 35 é a resposta.
Considere o seguinte vetor:
vetor < int > F = { - 4 , 10 , quinze , 9 , - 5 , - vinte , - 3 , - 12 , - 3 , 4 , 6 , 3 , dois , 8 , 3 , - 5 , - dois } ;
Existem dois sub-matrizes com somas máximas. A maior soma é aquela que é considerada como solução para o problema de submatriz máxima. As sub-matrizes são: {10, 15, 9} com uma soma de 34 e {4, 6, 3, 2, 8, 3} com uma soma de 26. Claro, a fatia com a soma de 34 é a resposta porque o problema é procurar o sub-array com a maior soma e não o sub-array com a maior soma.
Desenvolvendo o Algoritmo de Kadane
As informações nesta seção do tutorial não são o trabalho original de Kadane. É a própria maneira do autor de ensinar o algoritmo de Kadane. Um dos vetores acima, com seus totais em execução, está nesta tabela:
Dados | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | quinze | 4 | -8 | -quinze | -22 |
Execução total | 5 | 12 | 8 | -dois | -8 | -dois | 3 | 13 | 8 | 23 | 27 | vinte e um | 16 | -6 |
índice | 0 | 1 | dois | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | onze | 12 | 13 |
Running Total para um índice é a soma de todos os valores anteriores, incluindo o do índice. Existem duas sequências com somas máximas aqui. Eles são {5, 7}, que dá uma soma de 12, e {6, 5, 10, -5, 15, 4}, que dá uma soma de 35. A sequência que dá uma soma de 35 é o que se deseja .
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 sequências.
Assim, a ideia do algoritmo de Kadane é fazer o total em execução enquanto compara as somas máximas à medida que são encontradas, movendo da esquerda para a direita na matriz fornecida.
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}, o que dá 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 se deseja.
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 sequências.
Novamente, a ideia do algoritmo de Kadane é fazer o total em execução enquanto compara as somas máximas à medida que são encontradas, movendo-se da esquerda para a direita na matriz fornecida.
Código pelo Algoritmo de Kadane em C++
O código dado 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:
#include#include
usando o namespace std;
Há inclusão da biblioteca iostream, responsável pela entrada e saída. O namespace padrão é usado.
A ideia do algoritmo de Kadane é ter o total em execução enquanto compara as somas máximas à medida que são encontradas, movendo da esquerda para a direita na matriz fornecida. A função do algoritmo é:
int maxSunArray ( vetor < int > & UMA ) {int N = A.tamanho ( ) ;
int maxSoma = A [ 0 ] ;
int execuçãoTotal = A [ 0 ] ;
por ( int eu = 1 ; eu < N; i++ ) {
int tempRunTotal = runTotal + A [ eu ] ; // pode ser menor que A [ eu ]
E se ( UMA [ eu ] > tempRunTotal )
executarTotal = A [ eu ] ; // dentro caso UMA [ eu ] é maior que o total em execução
senão
runTotal = tempRunTotal;
E se ( runTotal > maxAmount ) // comparando todas as somas máximas
maxSum = runTotal;
}
Retorna maxAmount;
}
O tamanho, N da matriz fornecida (vetor) é determinado. 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.
Existe um for-loop principal. A varredura começa em 1 e não em zero por causa da inicialização das variáveis, maxSum e runTotal para A[0] que é o primeiro elemento do array fornecido.
No loop for, a primeira instrução determina um total de execução temporário adicionando o valor atual à soma acumulada de todos os valores anteriores.
Em seguida, há uma construção if/else. Se o valor atual sozinho for maior que o total em execução até o momento, esse valor único se tornará o total em execução. Isso é útil especialmente se todos os valores na matriz fornecida forem negativos. Nesse caso, o valor negativo mais alto sozinho se tornará o valor máximo (a resposta). Se o valor atual sozinho não for maior que o total de execução temporário até o momento, o total de execução se tornará o total de execução anterior mais o valor atual – esta é a parte else da construção if/else.
O último segmento de código no loop for escolhe 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 submatriz. Observe que o total em execução aumentaria e diminuiria, à medida que a matriz é varrida da esquerda para a direita. Ele cai à medida que atinge valores negativos.
A soma final máxima do sub-matriz escolhida é retornada após o loop for.
O conteúdo para uma função principal C++ adequada, para a função do algoritmo de Kadane é:
vetor < int > A = { 5 , - 7 , 3 , 5 , - dois , 4 , - 1 } ; // { 3 , 5 , - dois , 4 } - > 10int ret1 = maxSunArray ( UMA ) ;
cout << ret1 << fim;
vetor < int > B = { - dois , 1 , - 3 , 4 , - 1 , dois , 1 , - 5 , 4 } ; // { 4 , - 1 , dois , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << fim;
vetor < int > C = { 3 , dois , - 6 , 4 , 0 } ; // { 3 , dois } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << fim;
vetor < int > D = { 3 , dois , 6 , - 1 , 4 , 5 , - 1 , dois } ; // { 3 , dois , 6 , - 1 , 4 , 5 , - 1 , dois } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << fim;
vetor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , quinze , 4 , - 8 , - quinze , - 22 } ; // { 6 , 5 , 10 , - 5 , quinze , 4 } - > 35
int ret5 = maxSunArray ( E ) ;
cout << ret5 << fim;
vetor < int > F = { - 4 , 10 , quinze , 9 , - 5 , - vinte , - 3 , - 12 , - 3 , 4 , 6 , 3 , dois , 8 , 3 , - 5 , - dois } ; // { 10 , quinze , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << direito 6 << fim;
Com isso, a saída será:
10
6
5
vinte
35
3. 4
Cada resposta de linha aqui, corresponde a um determinado array, em ordem.
Conclusão
A complexidade de tempo para o algoritmo de Kadane é O(n), onde n é o número de elementos no array dado. Essa complexidade de tempo é a mais rápida para o problema de submatriz máxima. Existem outros algoritmos que são mais lentos. A ideia do algoritmo de Kadane é fazer o total em execução, enquanto compara as somas máximas à medida que são encontradas, movendo-se da esquerda para a direita na matriz fornecida. Se o valor atual sozinho for 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 de execução é o total de execução anterior mais o elemento atual, conforme previsto, à medida que a matriz fornecida é varrida.
Pode haver mais de uma soma máxima, para diferentes submatrizes possíveis. A soma máxima mais alta, para todas as sub-matrizes possíveis, é escolhida.
Quais são os índices limitantes para o intervalo da soma máxima escolhida? – Isso é discussão para outra hora!
Cris