이진 문자열 s가 있다고 가정합니다. 이제 문자열을 비어 있지 않은 두 개의 하위 문자열 s1과 s2로 분할하는 작업을 고려해 보겠습니다. 이 분할의 점수는 s1의 "0" 개수와 s2의 "1" 개수의 합입니다. 얻을 수 있는 최대 점수를 찾아야 합니다.
따라서 입력이 s ="011001100111"과 같으면 출력은 "01100" + "110111"과 같이 문자열을 분할할 수 있기 때문에 8이 됩니다. 그러면 점수는 3 + 5 =8입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
one :=s에 있는 "1"의 수
-
0 :=0
-
답변 :=0
-
범위 0에서 s - 2 사이의 i에 대해 수행
-
s[i]가 "0"과 같으면
-
0 :=0 + 1
-
-
그렇지 않으면
-
일 :=일 - 1
-
-
ans :=ans 및 (1 + 0)의 최대값
-
-
반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
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