이진 배열에서 가장 긴 연속 1 시퀀스를 얻기 위해 1로 바꿀 0의 인덱스 찾기 - Python의 Set-2

바이너리 배열이 하나 있다고 가정합니다. 1의 연속 시퀀스의 최대 수를 얻으려면 1로 대체될 수 있는 0의 위치를 ​​찾아야 합니다.

따라서 입력이 [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]과 같으면 출력은 10이 되므로 배열은 [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 나는 :=0,

• n :=A의 크기

• count_left :=0, count_right :=0

• max_i :=-1, last_i :=-1

• count_max :=0

• 내가

  • A[i]가 1과 같으면

    • count_right :=count_right + 1

  • 그렇지 않으면

    • last_i가 -1과 같지 않으면

      • count_right + count_left + 1> count_max인 경우

        • count_max :=count_left + count_right + 1

        • max_i :=last_i

    • last_i :=나는

    • count_left :=count_right

    • count_right :=0

  • 나는 :=나는 + 1

• last_i가 -1과 같지 않으면

  • count_left + count_right + 1> count_max인 경우

    • count_max :=count_left + count_right + 1

    • max_i :=last_i

• max_i를 반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def find_max_one_index(A):
   i = 0
   n = len(A)
   count_left = 0
   count_right = 0
   max_i = -1
   last_i = -1
   count_max = 0
   while i < n:
      if A[i] == 1:
         count_right += 1
      else:
         if last_i != -1:
            if count_right + count_left + 1 > count_max:
               count_max = count_left + count_right + 1
               max_i = last_i
            last_i = i
            count_left = count_right
            count_right = 0
      i += 1
   if last_i != -1:
      if count_left + count_right + 1 > count_max:
         count_max = count_left + count_right + 1
         max_i = last_i
   return max_i
A = [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]
print(find_max_one_index(A))

입력

[1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]

출력

10