Ozon go school

Прочитав на хабре про Школа Go от ozon захотел я податься. Вдохновила меня фраза из хабростатьи

Обучение в школе GO Ozon можно пройти совершенно бесплатно и по окончании получить оффер от Ozon или продолжить идти «своим путем», получив дополнительные знания и умения.

Я прошел тестовое,но после того как отписал что не собираюсь никуда релоцироваться, мне больше ничего так и не отписали, обидно =( Ну хоть в go чуть потренировался

А вот и само тестовое

Задача о длиной цепочке единиц

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Дана последоватльность 0 и 1
Нужно найти самую длинную последовательность из 1 (единиц) после удаления любого элемента

func maxOnesAfterRemoveItem([]byte) uint
assert(maxOnesAfterRemoveItem[0,0] == 0)
assert(maxOnesAfterRemoveItem[0,1] == 1)
assert(maxOnesAfterRemoveItem[1,0] == 1)
assert(maxOnesAfterRemoveItem[1,1] == 1)
assert(maxOnesAfterRemoveItem[1, 1, 0, 1, 1] == 4)
assert(maxOnesAfterRemoveItem[1, 1, 0, 1, 1, 0, 1, 1, 1] == 5)
assert(maxOnesAfterRemoveItem[1, 1, 0, 1, 1, 0, 1, 1, 1, 0] == 5)
Что хочется увидеть:

Алгоритм со сложностью O(N) по времени и O(1) по памяти

Первой мыслью както сюда динамическое программирование приплести, но фраза алгоритм сложностью O(N) подсказывала, что ожидается линейный перебор

А вот и решение

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

package main

import "fmt"

func maxOnesAfterRemoveItem(list []byte) uint {
	oneLength := uint(0)
	maxLen := uint(0)
	skipFirst0 := true
	skippedPrevZeroIndex := 0
	for i := 0; i < len(list); i++ {
		currentValue := list[i]
		if currentValue == 1 {
			oneLength = oneLength + 1
			if oneLength > maxLen {
				maxLen = oneLength
			}
		} else {
			if currentValue == 0 && skipFirst0 {
				skippedPrevZeroIndex = i
				skipFirst0 = false
				continue
			}
			if currentValue == 0 && !skipFirst0 {
				i = skippedPrevZeroIndex
				oneLength = 0
				skipFirst0 = true
			}
		}
	}
	if maxLen == uint(len(list)) {
		return maxLen - 1
	}
	return maxLen
}
func main() {
	fmt.Println(maxOnesAfterRemoveItem([]byte{0, 0}))
}