/* Kinā ir viena rinda ar vietām. Jaunais skatītājs izvēlas vietu, lai sēdētu pēc iespējas tālāk no citiem skatītājiem rindā. Tas ir, attālums no vietas, kur viņš sēdīs, līdz tuvākajam skatītājam, ir jābūt maksimālam. Ir garantēts, ka vienmēr ir brīvas vietas un ka jau ir sēdējis vismaz viens skatītājs. Uzrakstiet funkciju, kas, pamatojoties uz dotu vietu rindu (nulles un vienu masīvu), atgriezīs attālumu no izvēlētās vietas. Ievade: [1, 0, 0, 0, 0, 1] Izvade: 2 Ievade: [1, 0, 1, 0, 0, 1, 0, 0, 0, 1] Izvade: 2 Ievade: [1, 0, 1, 0] Izvade: 1 */

Funkcija ir jāatrod vieta (nulle ar indeksu), kur attālums līdz tuvākajai aizņemtajai vietai (viens) ir maksimāls.

Risinājuma ideja:

• Pārlūkot masīvu, katrai brīvai vietai aprēķināt attālumu līdz tuvākajai aizņemtajai vietai.
• Atgriezt šo maksimālo attālumu.

Optimizētais veids — viens pārejs ar aprēķinu attālumiem līdz tuvākajām vienībām pa kreisi un pa labi.

Piemērs Go valodā:

func maxDistance(biļetes []int) int {
    n := len(biļetes)
    kreisDist := make([]int, n)
    labDist := make([]int, n)

    // Aizpildīt attālumus līdz tuvākajai aizņemtajai vietai pa kreisi
    dist := n
    for i := 0; i < n; i++ {
        if biļetes[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        kreisDist[i] = dist
    }

    // Aizpildīt attālumus līdz tuvākajai aizņemtajai vietai pa labi
    dist = n
    for i := n - 1; i >= 0; i-- {
        if biļetes[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        labDist[i] = dist
    }

    maxDist := 0
    for i := 0; i < n; i++ {
        if biļetes[i] == 0 {
            // Minimālais attālums līdz tuvākajam skatītājam
            d := kreisDist[i]
            if labDist[i] < d {
                d = labDist[i]
            }
            if d > maxDist {
                maxDist = d
            }
        }
    }

    return maxDist
}

Tādējādi funkcija atgriezīs maksimālo attālumu līdz tuvākajam skatītājam izvēlētajā vietā.