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

Cho chuỗi nhị phân s. Tách chuỗi thành hai chuỗi con không rỗng s1 và s2. Điểm số = (số '0' trong s1) + (số '1' trong s2). Tìm điểm số lớn nhất có thể đạt được.

Ví dụ: s = "011001100111" → kết quả 8. Tách tại vị trí 5: "01100" (3 số 0) + "110111" (5 số 1) = 8.

Thuật toán giải quyết (O(n))

1. Đếm tổng số '1' trong chuỗi: ones = s.count("1")
2. Khởi tạo zeros = 0, ans = 0
3. Duyệt i từ 0 đến len(s)-2 (đảm bảo cả hai phần không rỗng):
   • Nếu s[i] == '0': zeros += 1
   • Ngược lại: ones -= 1
   • Cập nhật ans = max(ans, ones + zeros)
4. Trả về ans

Ví dụ minh họa

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