Não é possível entender a relevância de $\binom{n-1}{2}$ subarrays no Máximo Sub-matriz de Problema

Question

Recentemente, deparei com a frase do Livro Introdução aos Algoritmos 4.1 O máximo de sub-matriz de problema:

Ainda precisamos de seleção $\binom{n-1}{2} = heta(n^2)$ subarrays por um período de $n$ dias.

Aqui $n$ é o número de dias tomado como um exemplo para mostrar as alterações no preço das ações.

Podemos considerar que este é o tamanho de uma matriz A.

Onde estamos equipados com uma Matriz A e precisamos encontrar o valor líquido é de, no máximo a partir do primeiro dia ao último dia.

Para explicar, mais especificamente, isso significa que para uma matriz $A$ tamanho $n$ precisamos de seleção $\binom{n-1}{2}$ subarrays.

Mas, eu não posso entender como precisamos $\binom{n-1}{2}$ sub-matrizes?

Se tomarmos uma matriz de tamanho 5 alguém por favor poderia me explicar por que precisamos de apenas 6 sub-matrizes.Não sub-matrizes de ser:

[1...5]
[1...4]
[1...3]
[1...2]

[2...4]
[2...5]


[3...5]
[4...5]

Por favor, corrija-me se estou errado.Referências: Máximo Subarray Problema

Obrigado.

Answer 1

Você encontrou um bug em um dos mais famosos livros em ciência da computação!

---

Enquanto há $n$ dias, há apenas $n-1$ alterações no preço da ação.Portanto, há $\binom{n-1}{2}$ subarrays da matriz das alterações no preço das ações, assumindo que um subarray começa e termina em diferentes índices.

Que explicar, eu acredito, porque os livros diz que "ainda precisamos de seleção $\binom{n-1}{2} = heta(n^2)$ subarrays por um período de $n$ dias".

---

No entanto, na verdade, você está certo de que ainda precisamos verificar $\binom n2$ subarrays.

Deixe $B$ ser a matriz dos preços diários por um período de $n$, iniciando o índice (dia) 0.Deixe $A$, como no livro, ser a correspondente matriz das alterações de preço, iniciando o índice (dia) 1.Se você selecionar para comprar no dia $i$ e vender no dia $j$, fazendo um lucro de $B[j]-B[i]$, que corresponde a subarray $A[i+1\,..\,j]$, i.é., $(A[i+1], A[i+2], \cdots, A[j])$.Por favor, note que a alteração dos índices de $i$ e $j$ no $B$ para os índices de $i+1$ e $j$ no $A$.Enquanto $i$ e $j$ tem de ser diferentes sempre como "você está autorizado a comprar uma unidade de estoque apenas uma vez e, em seguida, vendê-lo em uma data posterior", $i+1$ e $j$ são os mesmos quando $j=i+1$, por exemplo, quando você vender no dia seguinte.

Deixe-nos a verificar a soma dos números selecionados em $A$ é, de fato, $B[j]-B[i]$. $$\begin{alinhado} &\quad A[i+1]+A[i+2]+\cdot+A[j]\\ &=(B[i+1]-B[j])+(B[i+2]-B[i+1])+\cdot+B[j]-B[j-1])\\ &=B[j]-B[i].\end{alinhado}$$ Observação a fórmula se mantém quando $j=i+1$.

Além do subarrays de $A$ que iniciar e terminar em índices diferentes, devemos considerar que o subarrays com o mesmo índice inicial e final do índice.Há $n-1$ um deles, por exemplo, o subarray cujo único elemento é $A[1]$, o subarray cujo único elemento é $A[2]$, ...e o subarray cujo único elemento é $A[n-1]$.Desde $\binom{n-1}2+(n-1)=\binom n2$, que ainda precisam de seleção $\binom n2$ subarrays.

Por exemplo, se os preços diários por um período de $3$ dias $B=(85, 105, 102)$, as alterações de preços $A=(20, -3)$.Se nós não verificar o subarray de $A$, $(20)$, que significa a compra no preço $85$ no dia $0$ e vendendo a preço $105$ no dia $1$, vamos perder o ideal de lucro, $20$.

---

Este simples e óbvio o erro não está listado no a página de erratas para Introdução aos Algoritmos, Terceira Edição.É incrível que este erro tem sido a viver confortavelmente em que livro popular por mais de dez anos antes que você apontou explicitamente.

Por outro lado, muitas pessoas podem ter sido conscientes de que o erro, embora eu não perceba isso.O foco de que a equivocada afirmação é "ainda precisamos de seleção $ heta(n^2)$ subarrays por um período de $n$ dias".O número real de subarrays que devem ser verificados, não é crítico, desde que o seu nível de crescimento assintótico é correto.Enquanto enganosa, caso contrário, esse erro não prejudica muito o desenvolvimento de um algoritmo melhor.