Considere uma matriz de bits, digamos

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0

Chamamos um sub-arranjo contíguo de comprimento ≥ 5 uma fase se pelo menos 85% dos bits forem iguais e o primeiro / último bits forem iguais ao bit maioritário. Além disso, chamamos uma fase de máximo se não for um sub-arranjo estrito de alguma outra fase.

Aqui estão as fases máximas do exemplo acima:

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0
      -------------
                    -------------
                        -------------

Como você pode ver, existem 3fases máximas. Por outro lado, isso

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0
                        ---------

não é uma fase máxima, pois é um sub-arranjo estrito de pelo menos uma outra fase.

O desafio

Entrada é uma sequência de ≥ 5 bits via STDIN, linha de comando ou argumento de função. Os bits podem aparecer como uma string ou uma matriz.

Você deve gerar um único número inteiro, o número máximo de fases da matriz, impresso via STDOUT ou retornado de uma função.

Pontuação

Isso é código-golfe, então o programa com o menor número de bytes vence.

Casos de teste

0 1 0 1 0 -> 0
0 0 0 0 0 -> 1
0 0 0 0 1 0 1 1 1 1 -> 0
0 0 0 0 0 1 0 1 1 1 1 1 -> 2
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 -> 1
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 -> 2
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 -> 1
0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 -> 0
1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 -> 4
0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 -> 5

Aqui está a explicação para o último caso:

0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0
---------------------------
      -------------------------
                            -----------------
                                -----------------
                                              -------------

^{Curiosidade: esse desafio surgiu de um problema de mineração de dados com o objetivo de detectar alterações nos dados temporais.}

Dyalog APL, 62 caracteres

{≢∪0~⍨+/∨⍀∨\⌽∘.{((⊃=⊃∘⌽)∧(.85≤(+/⊢=⊃)÷≢)∧5≤≢)(⍺-1)↓⍵↑a}⍨⍳⍴a←⍵}

Semelhante à solução de Zgarb, mas jogou um pouco mais.

Python 2, 149 bytes

a=input()
l=len(a)
n=p=0
for i in range(l):
 for j in range(l-1,i+3,-1):
  if(j>p)>(.15<sum(a[i:j+1])/(j+1.-i)+a[i]+a[j]<2.85):n+=1;p=j;break
print n

O primeiro loop varre a matriz da esquerda para a direita. Cada bit, indexado por i, é verificado para ver se poderia ser o primeiro bit em uma fase máxima.

Isso é feito pelo loop interno, que digitaliza da direita para a esquerda. Se a sub-matriz entre ie jé uma fase, aumentamos o contador e seguimos em frente. Caso contrário, continuamos até o subarray ficar muito pequeno ou j chegar ao final da fase máxima anterior.

1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0
i ->                               <- j

Exemplo:

$ python phase.py
[1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0]
3

Python 2, 144

Digite a entrada no formulário [0,1,0,1,0].

a=input()
o=[2];i=-1
while a[i:]:
 j=len(a);i+=1
 while j>i+4:o+=sum(j>max(o)>x==a[i]==a[j-1]for x in a[i:j])*20/(j-i)/17*[j];j-=1
print~-len(o)

As subseqüências são verificadas com a ordem aumentando o elemento inicial e depois diminuindo o comprimento. Dessa maneira, sabe-se que uma nova subsequência não é uma subsequência de uma subsequência anterior se o índice do seu último elemento for maior que qualquer índice do último elemento da sequência encontrada anteriormente.

Dyalog APL, 86 bytes *

{+/∨/¨∪↓∨⍀∨\{⊃({(.5>|k-⍵)∧.35≤|.5-⍵}(+/÷⍴)⍵)∧(5≤⍴⍵)∧(⊃⌽⍵)=k←⊃⍵}¨⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵}

Experimente aqui. Uso:

   f ← {+/∨/¨∪↓∨⍀∨\{⊃({(.5>|k-⍵)∧.35≤|.5-⍵}(+/÷⍴)⍵)∧(5≤⍴⍵)∧(⊃⌽⍵)=k←⊃⍵}¨⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵}
   f 0 0 0 0 0 1 0 1 1 1 1 1
2

Provavelmente isso pode ser bastante praticado, especialmente a parte do meio, onde a condição da fase é verificada.

Explicação

Primeiro coleciono as substrings do vetor de entrada em uma matriz, onde o canto superior esquerdo contém toda a entrada, usando ⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵. Para a entrada 0 0 0 0 0 1 0, essa matriz é

┌───────────────┬─────────────┬───────────┬─────────┬───────┬─────┬───┬─┐
│1 0 0 0 0 0 1 0│1 0 0 0 0 0 1│1 0 0 0 0 0│1 0 0 0 0│1 0 0 0│1 0 0│1 0│1│
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 0 0 0 1 0  │0 0 0 0 0 1  │0 0 0 0 0  │0 0 0 0  │0 0 0  │0 0  │0  │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 0 0 1 0    │0 0 0 0 1    │0 0 0 0    │0 0 0    │0 0    │0    │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 0 1 0      │0 0 0 1      │0 0 0      │0 0      │0      │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 1 0        │0 0 1        │0 0        │0        │       │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 1 0          │0 1          │0          │         │       │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│1 0            │1            │           │         │       │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0              │             │           │         │       │     │   │ │
└───────────────┴─────────────┴───────────┴─────────┴───────┴─────┴───┴─┘

Então mapeio a condição de ser uma fase sobre ela, resultando na matriz 0-1

0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Para obter o número de fases máximas, inunço as 1letras para a direita e para baixo usando ∨⍀∨\,

0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

colete as linhas exclusivas com ∪↓,

┌───────────────┬───────────────┐
│0 0 0 0 0 0 0 0│1 1 1 1 1 1 1 1│
└───────────────┴───────────────┘

e conte os que contêm pelo menos um 1usando +/∨/¨.

^{* Existe uma codificação padrão de 1 byte para APL.}

Clojure, 302

(defn p[v l](if(or(<(count v)5)(= 0 l))nil(if((fn[v](let[f(first v)c(apply + v)o(count v)r(/ c o)t(+ f f r)](and(= f(last v))(or(> t 2.85)(< t 0.15)))))v)0(let[r(p(vec(drop-last v))(dec l))](if r(+ r 1)r)))))(defn s[v l c](if(empty? v)c(let[n(p v l)](if n(s(vec(rest v))n(inc c))(s(vec(rest v))l c)))))

e a versão levemente não-gasta

(defn is-phase [vector]
  (let [f (first vector)
        c (apply + vector)
        o (count vector)
        r (/ c o)
        t (+ f f r)]
    (and (= f (last vector))
         (or (> t 2.85) (< t 0.15)))))
(defn phase-index [vector last]
  (if (or (<(count vector)5)(= 0 last)) nil
    (if (is-phase vector) 0
      (let [r (phase-index (vec(drop-last vector)) (dec last))]
        (if r (+ r 1) r)))))
(defn phase-count [vector last count]
  (if (empty? vector) count
    (let [n (phase-index vector last)]
         (if n (phase-count (vec(rest vector)) n (inc count))
             (phase-count (vec(rest vector)) last count)))))

que pode ser chamado assim: (s [0 1 0 1 0] 10 0). Requer alguns argumentos extras, mas eu poderia me livrar daqueles com mais 20 caracteres.

JavaScript (ES6) 141

O algoritmo do @ grc portado para JavaScript
Input pode ser uma string ou uma matriz

F=b=>
  (l=>{
    for(c=e=i=0;i<l;++i)
      for(j=l;j>i+4&j>e;--j)
        (k=0,[for(d of b.slice(i,j))k+=d==b[i]],k<(j-i)*.85)|b[i]-b[j-1]||(++c,e=j)
  })(b.length)|c

Teste no console do FireFox / FireBug

;['01010', '00000', '0000101111',
'000001011111', '100000000000010',
'0000010000010000010', '00000100000100000100',
'010100101010001111010011000110',
'111110000011111001000000001101',
'011000000000001011111110100000'].forEach(t => console.log(t,F(t)))

Saída

01010 0
00000 1
0000101111 0
000001011111 2
100000000000010 1
0000010000010000010 2
00000100000100000100 1
010100101010001111010011000110 0
111110000011111001000000001101 4
011000000000001011111110100000 5

CJam, 110 103 bytes

Muito tempo. Pode ser jogado muito.

q~_,,\f>{_,),5>\f<{:X)\0==X1b_X,.85*<!\.15X,*>!X0=!*\X0=*+&},:,W>U):U+}%{,(},_{{_W=IW=>\1bI1b>!&!},}fI,

Entrada é como

[0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0]

Saída é o número de fases.

Experimente online aqui

JavaScript (ECMAScript 6), 148 139 bytes

f=(s,l=0,e=0,p=0)=>{for(n=s.length,o=[j=0,y=0],i=l;i<n;++j>4&x==s[l]&i>e&c>=.85‌​*j&&(e=i,y=1))c=++o[x=s[i++]];return l-n?f(s,l+1,e,p+y):p}

Recursa pela matriz e inicia a iteração no último índice de recursão. O argumento pode ser uma matriz ou sequência.

f('011000000000001011111110100000'); //5

Wolfram - 131

{x_, X___}⊕{Y__, x_, y___}/;MemberQ[t={x, X, Y, x}, 1-x] && t~Count~x > .85 Length@t := 
  1 + {X, Y, x}⊕{y} 
{_, X___}⊕y_ := {X}⊕y
{}⊕{y_, Y__} := {y}⊕{Y}
_⊕_ := 0

Exemplo

{}⊕{1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0}
> 3
{}⊕{0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0}
> 5

Java: 771 bytes

import java.util.*;public class A{static int[]a;static class b{int c,d,e,f,g,h;b(int i,int j){this.c=i;this.d=j;this.h=j-i+1;this.e=k();this.f=this.h-this.e;this.g=e>f?1:0;}
boolean l(b n){return this.c>=n.c&&this.d<=n.d;}
int k(){int o=0;for(int i=c;i<=d;i++){if(a[i]==1){o++;}}
return o;}
public boolean equals(Object o){b x=(b)o;return x.c==this.c&&x.d==this.d;}
float p(){if(g==0){return(float)f/h;}else{return(float)e/h;}}
boolean q(){float r=p();return a[c]==a[d]&&a[d]==g&&r>=0.85F;}}
static int s(int[]t){a=t;List<b>u=new ArrayList<>();for(int v=0;v<t.length-4;v++){int x=v+4;while(x<t.length){b y=new b(v,x);if(y.q()){u.add(y);}
x++;}}
List<b>a=new ArrayList<>();for(b c:u){for(b d:u){if(!c.equals(d)&&c.l(d)){a.add(c);break;}}}
u.removeAll(a);return u.size();}}

executado chamando o método s (int [] input)