3499.操作后最大活跃区段数I

https://leetcode.cn/problems/maximize-active-section-with-trade-i/

给你一个长度为 n 的二进制字符串 s，其中：

'1' 表示一个活跃区段。
'0' 表示一个 非活跃 区段。

你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：

将一个被 '0' 包围的连续 '1' 区块转换为全 '0'。
然后，将一个被 '1' 包围的连续 '0' 区块转换为全 '1'。

返回在执行最优操作后，s 中的最大活跃区段数。

注意：处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。

示例 1：

输入： s = "01"

输出： 1

解释：

因为没有被 '0' 包围的 '1' 区块，因此无法进行有效操作。最大活跃区段数为 1。

示例 2：

输入： s = "0100"

输出： 4

解释：

字符串 "0100" → 两端加上 '1' 后得到 "101001" 。
选择 "0100"，"10**1**001" → "1**0000**1" → "1**1111**1" 。
最终的字符串去掉两端的 '1' 后为 "1111" 。最大活跃区段数为 4。

示例 3：

输入： s = "1000100"

输出： 7

解释：

字符串 "1000100" → 两端加上 '1' 后得到 "110001001" 。
选择 "000100"，"11000**1**001" → "11**000000**1" → "11**111111**1"。
最终的字符串去掉两端的 '1' 后为 "1111111"。最大活跃区段数为 7。

示例 4：

输入： s = "01010"

输出： 4

解释：

字符串 "01010" → 两端加上 '1' 后得到 "1010101"。
选择 "010"，"10**1**0101" → "1**000**101" → "1**111**101"。
最终的字符串去掉两端的 '1' 后为 "11110"。最大活跃区段数为 4。

提示：

1 <= n == s.length <= 10^5
s[i] 仅包含 '0' 或 '1'

python

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        n = len(s)
        base = s.count('1')
        best = base  # 不操作的结果

        i = 0
        while i < n:
            if s[i] == '1':
                # 找到连续1的区块 [i, j]
                j = i
                while j + 1 < n and s[j+1] == '1':
                    j += 1
                # 判断该1区块是否被0包围（注意两侧必须在 s 内部，即 i>0 且 j<n-1）
                if i > 0 and j < n - 1 and s[i-1] == '0' and s[j+1] == '0':
                    # 计算该区块左侧连续0的数量
                    left = 0
                    k = i - 1
                    while k >= 0 and s[k] == '0':
                        left += 1
                        k -= 1
                    # 计算该区块右侧连续0的数量
                    right = 0
                    k = j + 1
                    while k < n and s[k] == '0':
                        right += 1
                        k += 1
                    # 若执行操作，最终这部分将全部变成1，因此增益为左右两侧0的总数
                    best = max(best, base + left + right)
                i = j + 1
            else:
                i += 1
        return best


if __name__ == "__main__":
    sol = Solution()
    print(sol.maxActiveSectionsAfterTrade("1000100"))  # 输出 7

3499.操作后最大活跃区段数I ​

3499.操作后最大活跃区段数I