Python - проблема с монетами при использовании петель не работает

Question

У меня есть некоторый код Python, над которым я работал несколько дней, и я думаю, что близок к тому, чтобы выяснить это, но некоторые пройденные тестовые значения не дают правильного ответа. Цель состоит в том, чтобы дать список 0 и 1, представляющих монеты. Программа определит максимальное количество смежных монет, которое может быть достигнуто после подбрасывания только одной монеты.

Например, для данного массива A, состоящего из шести чисел:

A = [1, 1, 0, 1, 0, 0]

, функция возвращает 4 Приведенный ниже код работает с этим примером, но если я ввожу список, такой как

A = [0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1]

, я получаю 9 вместо того, что должно быть 7. Я не уверен, что именно не так, но любая помощь ценится.

def solution(A):
    n = len(A)
    result = 0
    for i in range(n - 1):
        if (A[i + 1] == A[i]):
            result = result + 1
    r = -1
    for i in range(n):
        count = 0
        if (i > 0):
            if (A[i - 1] != A[i]):
                count = count + 1
            else:
                count = count - 1
        if (i < n - 1):
            if (A[i + 1] != A[i]):
                count = count + 1
            else:
                count = count - 1
        r = max(r, count)
    return result + r

Answer 1

В настоящее время вы не выглядите так, как будто находитесь в правильном направлении (если я что-то упустил). Вы можете решить эту проблему двумя способами. Первый способ проще, второй - более элегантный.

1. Просто переверните каждый элемент и сосчитайте максимальное количество смежных 0 с и 1 с. Это будет решение O(N^2).
2. Подсчет количества "островков" 0 с и 1 с. Затем итерируйте по этим числам. Таким образом, вы можете найти свой ответ за линейное время. Например, скажем, у вас есть

A = [0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1]

, это даст вам

islands = [2,3,1,1,5,1]

, что означает, что у вас есть: 2 0 с, 3 1 с, 1 1, 1 0, 5 0 с, 1 1. Затем переберите islands и проверьте, насколько вы можете расширить каждый остров. Т.е.

1. Первый остров: 2 0 с. Можно сделать 3 0 с, щелкнув A[2]
2. Второй остров: 3 1 с. Можно сделать 5 1 с, перевернув A[5]
3. Третий остров: 1 0 ....
4. Четвертый остров: 1 1 ....
5. Пятый остров: 5 0 с. Можно сделать 7 1 с, перелистывая A[6]
6. ...

Я могу дать вам больше подсказки / кода, если хотите.