Ha habido mucha confusión sobre lo que es una máxima de la subcadena, así que voy a explicar. Lo que el problema es llegar, es que si tuviéramos $11100100$, por ejemplo, tendría una subcadena que es un número impar de $0$'s, pero este no es uno de los máximos subcadenas. La máxima subcadenas en este caso sería $111$, $00$, $1$, y $0$.
De todos modos, Este es un problema clásico, y demuestra una genial relación entre los números de Fibonacci y los números del triángulo de Pascal.
La primera cosa a darse cuenta cuando se mira en esta pregunta es que todos los de la $0$'s debe venir en grupos de a $2$, o de lo contrario se estaría en un grupo de un número impar.
Podemos entonces construir las secuencias de la siguiente manera.
$$n=0\rightarrow []$$
$$n=1 \rightarrow (n=0) + 1 \rightarrow[1]$$
$$n=2 \rightarrow (n=0)+00 \text{ or }(n=1) + 1 \rightarrow [00]\text{ or } [11]$$
$$n=3 \rightarrow (n=1) + 00 \text{ or } (n=2) +1\rightarrow[100] \text{ or } [001,111]$$
$$n=4 \rightarrow (n=2) +00 \text{ or }(n=3)+1\rightarrow[0000,1100] \text{ or } [1001,0011,1111]$$
Como se puede ver, podemos agregar dos $0$'s hasta el final de los casos en $n-2$ o podemos agregar un $1$ hasta el final de los casos en $(n-1)$ para obtener la cantidad total de casos de $n$. Por lo tanto tenemos la recursividad de Fibonacci.
$$F_n=F_{n-1}+F_{n-2}$$
Ahora veamos la otra forma de hacerlo, es decir, por contar. Nos volverá a emplear la observación de que $0$'s debe venir en pares y podemos escribir esto como una suma de elegir notaciones.
Para $0$ pares de $0$'s, tenemos $n\choose 0$ combinaciones, como tenemos n todos los bloques de la misma.
Para $1$ par de $0$'s, tenemos $n-1 \choose 1$, como las que ahora sólo tenemos $n-1$ bloques, uno de los cuales es diferente.
Para 2 pares de $0$'s, tenemos $n-2 \choose 2$, como hemos $n-2$ bloques, dos de los cuales es diferente.
Continuar este patrón, se puede escribir como la suma de estos
$$\sum_{k=0}^{\left \lfloor{n/2}\right \rfloor} {n-k \choose k}$$
Este problema, colocado como está en el comienzo de un libro introductorio sobre la combinatoria, es probablemente significaba tener estas dos soluciones, que da paso a la siguiente igualdad increíble
$$\sum_{k=0}^{\left \lfloor{n/2}\right \rfloor} {n-k \choose k}=F_n$$
