/* De plaatsen in de bioscoop zijn in één rij gerangschikt. De net aangekomen kijker kiest een plek om zo ver mogelijk van de andere kijkers in de rij te zitten. Dat wil zeggen, de afstand van de plek waar hij zit tot de dichtstbijzijnde kijker moet maximaal zijn. Er wordt gegarandeerd dat er altijd vrije plaatsen zijn en dat er al minstens één kijker zit. Schrijf een functie die, op basis van een gegeven rij plaatsen (een array van nullen en enen), de afstand vanaf de gekozen plek teruggeeft. Invoer: [1, 0, 0, 0, 0, 1] Uitvoer: 2 Invoer: [1, 0, 1, 0, 0, 1, 0, 0, 0, 1] Uitvoer: 2 Invoer: [1, 0, 1, 0] Uitvoer: 1 */

De functie moet de plek vinden (index met nul) waar de afstand tot de dichtstbijzijnde bezette plek (en) maximaal is.

Oplossingsidee:

• Loop door de array, bereken voor elke vrije plek de afstand tot de dichtstbijzijnde bezette plek.
• Geef deze maximale afstand terug.

De optimale manier is één doorloop met het tellen van de afstanden tot de dichtstbijzijnde enen links en rechts.

Voorbeeld in Go:

func maxDistance(zitplaatsen []int) int {
    n := len(zitplaatsen)
    linksDist := make([]int, n)
    rechtsDist := make([]int, n)

    // Vul de afstanden tot de dichtstbijzijnde bezette plek links in
    dist := n
    for i := 0; i < n; i++ {
        if zitplaatsen[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        linksDist[i] = dist
    }

    // Vul de afstanden tot de dichtstbijzijnde bezette plek rechts in
    dist = n
    for i := n - 1; i >= 0; i-- {
        if zitplaatsen[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        rechtsDist[i] = dist
    }

    maxDist := 0
    for i := 0; i < n; i++ {
        if zitplaatsen[i] == 0 {
            // Minimale afstand tot de dichtstbijzijnde toeschouwer
            d := linksDist[i]
            if rechtsDist[i] < d {
                d = rechtsDist[i]
            }
            if d > maxDist {
                maxDist = d
            }
        }
    }

    return maxDist
}

Zo geeft de functie de maximale afstand tot de dichtstbijzijnde toeschouwer voor de gekozen plek.