Битмен ищет битовый баланс у двоичной строки (строки, состоящей только из
0 и
1). Чтобы найти битвой баланс, Битмен разбивает строку на две непустые подстроки (левую подстроку и правую подстроку). Затем Битмен считает сумму количества нулей в левой подстроке и количества единиц в правой подстроке. Битовый баланс двоичной строки равен максимальной сумме, полученной после какого-либо разбиения строки на подстроки.
Формат входных данных
На вход подается строка (2 <= длина строки <= 1000). Строка состоит только из символов
0 и
1.
Формат выходных данных
Выведите одно число - битовый баланс строки.
Примечание
В тестовом примере все возможные способы разить строку на 2 непустые строки следующие:
left = "0" и right = "11101", сумма = 1 + 4 = 5
left = "01" и right = "1101", сумма = 1 + 3 = 4
left = "011" и right = "101", сумма = 1 + 2 = 3
left = "0111" и right = "01", сумма = 1 + 1 = 2
left = "01110" и right = "1", сумма = 2 + 1 = 3
Битовый баланс равен максимальному значению суммы, следовательно ответ 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
011101
|
5
|