O que é exatamente um vazio Sub-matriz

Question

Eu li a pergunta no Exercício 4.1-4 na Introdução Aos Algoritmos:

Suponha que alterar a definição de máximo-subarray problema para que o resultado seja um vazio subarray, onde a soma dos valores de um vazio subarray é 0.Como você alterar qualquer um dos algoritmos que não permitem vazio subarrays para permitir um vazio subarray ser o resultado?

Eu não posso obter o que é um vazio sub-matriz.

Me deparei com o ponto de que um número pode ser retornado se a matriz é composta de elementos negativos só.

Por favor, alguém pode explicar o conceito de um vazio sub-matriz?E como podemos ter um vazio sub-matriz?

Mesmo se um único elemento é retornado, ele ainda significa que a sub-matriz é não vazio.Por favor, desmarque a dúvida.

Editar:

Para tornar mais claro como uma pergunta, se eu pegar uma matriz de elementos:

[-3,-4,-1,-8]

A resposta seria -1 ou 0?Por favor, explicar-se por que deve ser 0 e como podemos celebrar um vazio sub-matriz.

Obrigado.

Answer 1

Se você tem esta matriz: $[-2,-10,-5]$, e o problema especifica que você deve retornar a soma do máximo de subarray cujo comprimento é, no mínimo, $1$, você irá retornar a soma dos subarray $[-2]$, o que é $-2$.Tão longe, tão bom?

Agora, o foco aqui, porque este é o lugar onde você está, provavelmente, a ter problemas:

O problema agora é ajustado.O problema agora permite que você retorne a ele um vazio subarray, o que significa que, você pode retornar a ele um subarray que está vazia - um subarray que não tem elementos.Tenha paciência comigo:

Em matemática, um "vazio soma" é uma soma em que o número de termos é zero. Verifique.

Da mesma forma, em ciência da computação, um "vazio subarray" é um subarray em que o número de termos é zero. Esta é apenas a definição. É apenas um subarray cuja soma avalia a zero.

Agora, sobre a versão ajustada do problema, o que seria melhor, retornando a ele $[-2]$ cuja soma avalia a $-2$, ou devolver o vazio subarray $( [ \ \ \ ] )$ cuja soma avalia a $0$?

Answer 2

Um subarray de comprimento zero é vazia.

Dada uma matriz $A[1],\ldots,A[n]$, um subarray é especificado por um par de índices de $i \leq j$.Estes correspondem ao subarray $A[i],\ldots,A[j]$ de comprimento $j-i+1$.Se nós também permitir $j = i-1$ em seguida, obtemos um vazio subarray de comprimento $j-i+1 = 0$, cuja soma é zero.

---

No máximo subarray problema, é-nos dada uma matriz $A[1],\ldots,A[n]$, e quer encontrar um subarray cuja soma é o máximo.Se não permitimos vazio subarrays, isso significa que nós estamos olhando para o valor máximo de $$ A[i] + \cdots + A[j], $$ onde $1 \leq i \leq j \leq n$.Se estamos permitindo vazio subarrays, em seguida, tomamos o máximo do que com $0$, que é a soma de vazio subarray.

Isso só faz diferença se todas as entradas da matriz são negativos.O valor máximo de um não-vazio subarray é, neste caso, a máxima elemento $A[i]$, que é a soma dos subarray $A[i]$ de comprimento $1$.O vazio subarray, no entanto, tem uma grande soma: $0$.Portanto, se o vazio subarray não é permitido, a resposta deve ser $\max_i A[i]$, e se for permitido, a resposta deve ser $0$.