/* Kinijoje vietos išdėstytos vienoje eilėje. Naujas žiūrovas pasirenka vietą, kad sėdėtų kuo toliau nuo kitų žiūrovų eilėje. Tai reiškia, kad atstumas nuo vietos, kur jis sės, iki artimiausio žiūrovo, turi būti maksimalus. Yra garantija, kad visada yra laisvų vietų ir jau sėdi bent vienas žiūrovas. Parašykite funkciją, kuri pagal duotą vietų eilę (masyvą iš nulio ir vieno) grąžins atstumą nuo pasirinktos vietos. Įvestis: [1, 0, 0, 0, 0, 1] Išvestis: 2 Įvestis: [1, 0, 1, 0, 0, 1, 0, 0, 0, 1] Išvestis: 2 Įvestis: [1, 0, 1, 0] Išvestis: 1 */

Funkcija turi rasti vietą (nulinį indeksą), kur atstumas iki artimiausios užimtų vietų (vienetų) yra didžiausias.

Sprendimo idėja:

• Pereiti per masyvą, kiekvienai laisvai vietai apskaičiuoti atstumą iki artimiausios užimtų vietų.
• Grąžinti šį maksimalų atstumą.

Optimizuotas būdas — vienas perėjimas su skaičiavimu atstumų iki artimiausių vienetų kairėje ir dešinėje.

Pavyzdys Go kalba:

func maxDistance(sedynes []int) int {
    n := len(sedynes)
    kairDist := make([]int, n)
    dešinDist := make([]int, n)

    // Užpildyti atstumus iki artimiausios užimtų vietų kairėje
    dist := n
    for i := 0; i < n; i++ {
        if sedynes[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        kairDist[i] = dist
    }

    // Užpildyti atstumus iki artimiausios užimtų vietų dešinėje
    dist = n
    for i := n - 1; i >= 0; i-- {
        if sedynes[i] == 1 {
            dist = 0
        } else {
            dist++
        }
        dešinDist[i] = dist
    }

    maxDist := 0
    for i := 0; i < n; i++ {
        if sedynes[i] == 0 {
            // Mažiausias atstumas iki artimiausio žiūrovo
            d := kairDist[i]
            if dešinDist[i] < d {
                d = dešinDist[i]
            }
            if d > maxDist {
                maxDist = d
            }
        }
    }

    return maxDist
}

Taip funkcija grąžins maksimalią atstumą iki artimiausio žiūrovo pasirinktoje vietoje.