We can obtain $$$n$$$ from the binary representation as following

We know that the fact

Let’s consider the last active bit i.e. $$$\mathtt{1}$$$ is $$$i$$$ then $$$n$$$ as integer is

thus the answer is the index of last occurrence of $$$\mathtt{1}$$$ , Complexity $$$O(n)$$$.

for _ in range(int(input())):
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        if(s[i]=='1'):
            ans=n-i-1
            break
    print(ans)

Maintain two arrays $$$b$$$ and $$$c$$$ such that

Now , maintain a function $$$f$$$ that process the maximum subarray sum in $$$O(n)$$$ for both of arrays $$$b$$$ and $$$c$$$ (Kadane's Algorithm for example), be careful of initialization that it’s non-empty , and the answer is $$$\max(f(b),f(c))$$$.