LeetCode 解題筆記：3499. Maximize Active Section with Trade I

作者：王一哲
日期：2026年7月21日


LeetCode 題目連結：3499. Maximize Active Section with Trade I

解題想法

中等難度題，題目給一個只包含 0、1 的字串 $s$，可以對 $s$ 操作 1 次，過程為

1. 取一段連續的 1，其兩側皆為連續的 0，將中間的 1 全部改成 0。
2. 再將上個步驟取出的 3 段都改成 1。

題目要計算操作後 $s$ 之中最多可以有幾個 1。因為以上的操作並不會讓原來的 1 消失，反而是兩側的 0 變成 1，如果要使操作後的 1 數量最多，就是要找出兩段 0 數量相加的最大值。解題時先依照題義補上兩側的 1，儲存成新的字串 $t$。接下來計算連續出現的 0, 1 長度，儲存至串列 $rle$。最後找出最大增益，取連續兩段 0 的總長度最大值 $imax$，回傳 $s$ 之中 1 的數量加上 $imax$。

Python 程式碼

Runtime: 561 ms, beats 85.98%. Memory: 21.08 MB, beats 61.68%.

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        t = "1" + s + "1"  # 依照題義補上兩側的 1
        n = len(t)  # 長度，s 的內容為 1 ~ n-2
        
        # --- 計算連續出現的 0, 1 長度 ---
        rle = []  # 遊程編碼，run-length encoding
        curr = '1'  # 目前的字元，最左側是 1
        cnt = 1  # 數量
        for i in range(1, n):  # 掃過字串 t
            if t[i] == curr:  # 相同的字元
                cnt += 1  # 數量加 1
            else:  # 不同的字元，結算前一段
                rle.append(cnt)
                curr = t[i]
                cnt = 1
        rle.append(cnt)  # 結算最後一段

        # --- 找出最大增益，取連續兩段 0 的總長度最大值 ---
        imax, m = 0, len(rle)  # 最大值，rle 長度
        for i in range(2, m-2, 2):  # i 只找 1 所在的位置，排除兩端
            imax = max(imax, rle[i-1] + rle[i+1])
        # 答案為 s 之中 1 的數量加上 imax
        return s.count('1') + imax

C++ 程式碼

Runtime: 75 ms, beats 48.65%. Memory: 129.35 MB, beats 24.32%.

class Solution {
public:
    int maxActiveSectionsAfterTrade(string s) {
        string t = "1" + s + "1";  // 依照題義補上兩側的 1
        int n = (int)t.size();  // 長度，s 的內容為 1 ~ n-2
        
        /* 計算連續出現的 0, 1 長度 */
        vector<int> rle;  // 遊程編碼，run-length encoding
        char curr = '1';  // 目前的字元，最左側是 1
        int cnt = 1;  // 數量
        for(int i = 1; i < n; i++) {  // 掃過字串 t
            if (t[i] == curr) {  // 相同的字元
                cnt++;  // 數量加 1
            } else {  // 不同的字元，結算前一段
                rle.push_back(cnt);
                curr = t[i];
                cnt = 1;
            }
        }
        rle.push_back(cnt);  // 結算最後一段

        /* 找出最大增益，取連續兩段 0 的總長度最大值 */
        int imax = 0, m = (int)rle.size();  // 最大值，rle 長度
        for(int i = 2; i < m-2; i += 2) {  // i 只找 1 所在的位置，排除兩端
            imax = max(imax, rle[i-1] + rle[i+1]);
        }
        // 答案為 s 之中 1 的數量加上 imax
        return count(s.begin(), s.end(), '1') + imax;
    }
};