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

Problema Maximo De Sub Matriz 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 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 } - > 10
int 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