Digamos que nos dan una matriz [1,2,3,4], el número de subarreglos de al menos tamaño k = 3 es 3.
Es decir
[1,2,3],[1,2,3,4],[2,3,4]
De manera similar, para array = [1,2,3,4,5], el número de subarreglos de al menos tamaño k=3 es 6.
123,1234,12345,234,2345,345
¿Cómo podemos generalizar esto?
digamos que nes la longitud de la matriz. Si cuenta el número de subarreglo con exactamente la longitud k, puedes calcular fácilmente que sería igual a: n − k + 1
Luego, solo necesita hacer un sumatorio para valores más altos de khasta n, y obtenga que el número de subarreglos con al menos tamaño kes igual a:
norte ∑ yo=knorte-yo+1
Aquí hay una demostración visual de la respuesta de Alexandro Palacios y su segundo ejemplo:
| Longitud 3 | Longitud 4 | Longitud 5 |
|---|---|---|
| 123 | 1234 | 12345 |
| 234 | 2345 | |
| 345 |
Para ver por qué esto es igual a ( n − k + 22 ), como sugiere coffeemath, considere la siguiente copia de la tabla anterior, junto con un reflejo, indicado con estrellas:
123 1234 12345 234 2345 ∗ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 345 ∗ ∗ ∗ ∗ ∗
Claramente hay 4 ∗ 3 / 2entradas en la tabla, que es igual a ( n − k + 2 ) ( n − k + 2 − 1 ) / 2 = ( n − k + 22 )
Mor A.