Chương trình tìm điểm tối đa bằng cách chia chuỗi nhị phân thành hai phần trong Python

Giả sử chúng ta có một chuỗi nhị phân s. Bây giờ chúng ta hãy xem xét một phép toán, trong đó chúng ta chia chuỗi thành hai chuỗi con không trống là s1 và s2. Điểm của phép chia này là tổng của số "0" trong s1 và tổng của "1" ở s2. Chúng tôi phải tìm ra điểm số tối đa mà chúng tôi có thể đạt được.

Vì vậy, nếu đầu vào là s =​​"011001100111", thì đầu ra sẽ là 8, vì chúng ta có thể chia chuỗi như "01100" + "110111". Khi đó, điểm là 3 + 5 =8.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• những cái:=số "1" s trong s

• số không:=0

• ans:=0

• đối với tôi trong phạm vi từ 0 đến kích thước của s - 2, hãy thực hiện

  • nếu s [i] giống "0" thì

    • số không:=số không + 1

  • nếu không,

    • những cái:=cái - 1

  • ans:=tối đa ans và (một + số không)

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

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))

Đầu vào

"011001100111"

Đầu ra

8