Maximize Difference in a Binary Substring

Given a non-empty binary string S consisting of characters '0' and '1', find a non-empty contiguous substring T such that the difference between the number of 0's and the number of 1's is maximized. In other words, if we define

$$\Delta = \text{count}(0) - \text{count}(1)$$

for a substring, your task is to output the maximum possible value of \(\Delta\) among all non-empty contiguous substrings of S.

inputFormat

The input consists of a single line containing the binary string S, where S is non-empty and contains only the characters '0' and '1'.

outputFormat

Output the maximum difference, that is, the maximum value of \(\text{count}(0)-\text{count}(1)\) over all non-empty contiguous substrings of S.

Formally, if T is a contiguous substring of S, find and output

$$\max_{T \subseteq S, T \neq \emptyset} \Big(\text{count}(0) - \text{count}(1)\Big).$$

sample

101

1