โปรแกรมหาคะแนนสูงสุดจากการแบ่ง Binary String สองส่วนใน Python

ให้ Binary String s แบ่งเป็น s1 และ s2 (ทั้งคู่ไม่ว่าง) คะแนน = จำนวน '0' ใน s1 + จำนวน '1' ใน s2 หาคะแนนสูงสุด

ตัวอย่าง: s = "011001100111" → 8 (แบ่ง "01100" + "110111" → 3+5=8)

ขั้นตอน (One Pass O(n))

1. นับ ones ทั้งหมดใน s
2. zeros = 0, ans = 0
3. วนลูป i จาก 0 ถึง len(s)-2:
   • ถ้า s[i]=='0': zeros += 1
   • มิฉะนั้น: ones -= 1
   • ans = max(ans, ones + zeros)

ตัวอย่างโค้ด

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))  # Output: 8

อินพุต

"011001100111"

เอาต์พุต

8