Algoritmo per trovare la regione con densità meno probabile

Considera il seguente array booleano dove dark == true:

Inquestoscenariolaprobabilitàcheunacellasiascuraochiaraè50/50,maquestopotrebbenonessereveronelcasogenerale.

Massimizzandosolosulladensità,vediamochelecelleda12a16(incluse)hannol'areapiùgrandeconunacoperturaal100%albuio.Utilizzando questo calcolatore di probabilità binomiale troviamo che il valore p per trovare 5 celle oscure contigue (P (X > = 5)) è 0,03125.

Tuttavia, nelle celle da 12 a 21 la densità non è 100%, ma il valore p complessivo è inferiore (ad esempio, meno probabilità che la densità di questa regione si sia verificata casualmente). Ci sono 9 celle scure su 10 celle totali, che producono un valore p di 0.0107421875.

Vorrei un algoritmo che trovi in modo efficace la regione di densità meno probabile.

Tenere presente che questo array può essere grande e che ci possono essere regioni di luce densamente improbabile vicino a regioni scure densamente improbabili, in modo che le regioni combinate abbiano rapporti bilanciati chiaro / scuro. Mi piace così:

Ilnumerodipossibiliregioniall'internodiunamatricedidimensioneNè1+2+..+N=(N+1)N/2checidàunacomplessitàlegatasuperiorediO(N^2).Esistonoalgoritmiconcomplessitàinferiore?

EDIT1:riformulatointerminidilanciodimonete:cisonoduemonete.Unoègiusto,eunoèponderatoperveniretestalamaggiorpartedeltempo.Qualcunogiralamonetagiustaperdiversilanci,giralamonetaponderataperdiversilanci,poitornaalanciarelamonetagiusta.Tuttoquellocheabbiamoèilrecorddilanci.Comepossiamoindovinarelaregionenellalistaincuièstatautilizzatalamonetaponderata?

Questopotrebbeessereunproblemaapertoinquantoquestoera recentemente coperto come area per l'apprendimento automatico. ML a parte, sono curioso di sapere quale sia l'algoritmo deterministico di complessità più bassa.