Pythonでバイナリ文字列を2つの部分に分割して最大スコアを見つけるプログラム

バイナリ文字列sがあるとします。ここで、文字列を2つの空でないサブ文字列s1とs2に分割する操作について考えてみましょう。この分割のスコアは、s1でカウントされる「0」の合計とs2でカウントされる「1」の合計です。取得できる最大スコアを見つける必要があります。

したがって、入力がs ="011001100111"の場合、文字列を "01100" + "110111"のように分割できるため、出力は8になります。その場合、スコアは3 + 5=8です。

これを解決するには、次の手順に従います-

• ones：=s内の「1」の数

• ゼロ：=0

• ans：=0

• 0からs-2のサイズのiの場合、実行

  • s[i]が"0"と同じ場合、

    • ゼロ：=ゼロ+ 1

  • それ以外の場合

    • もの：=もの-1

  • ans：=ansと（1 + 0）の最大値

• ansを返す

例

理解を深めるために、次の実装を見てみましょう

def solve(s):
   ones = s.count("1")
   zeros = 0
   ans = 0
   for i in range(len(s) - 1):
      if s[i] == "0":
         zeros += 1
      else:
         ones -= 1
      ans = max(ans, ones + zeros)
   return ans

s = "011001100111"
print(solve(s))

入力

"011001100111"

出力

8