題目網址：https://leetcode.cn/problems/max-consecutive-ones-ii/

題意：給一 binary array nums, 你最多能反轉一個 0, 返回最大連續 1 的個數。

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
  • flip[i] 為 nums[1:i] 中某個元素反轉後, nums[i] = 1 的最大連續 1 個數
  • noFlip[i] 為 nums[1:i] 中沒有任何元素反轉, nums[i] = 1 的最大連續 1 個數

2. 得到狀態轉移方程：

  • 當 nums[i] == 0：
    • flip[i] 必須使 nums[i] = 1, 故將 flip 的次數用在 nums[i] 上
      ➔ flip[i] = noFlip[i - 1] + 1
    • noFlip[i] 必須使 nums[i] = 1, 但是在不 flip 的情況下, nums[i] 不可能為 1
      ➔ noFlip[i] = 0
  • 當 nums[i] == 1：
    • flip[i] 必須使 nums[i] = 1, 但 nums[i] 已經是 1, 故直接接上
      ➔ flip[i] = flip[i - 1] + 1
    • noFlip[i] 必須使 nums[i] = 1, 但 nums[i] 已經是 1, 故直接接上
      ➔ noFlip[i] = noFlip[i - 1] + 1

3. 初始化：

  • flip[0]、noFlip[0]：沒有任何元素時, 最大連續 1 個數為 0

  • flip[1]：根據定義, 先將 nums[1] 取 flip, 然後計算 nums[1] = 1 的最大連續 1 個數

    • 當 nums[1] = 0 時, 先取 flip 得 nums[1] = 1 ➔ flip[1] = 1
    • 當 nums[1] = 1 時, 先取 flip 得 nums[1] = 0 ➔ flip[1] = 0

    ➔ 由上述得到 flip[1] = 1 - nums[1]（nums[1] 取 flip）

  • noFlip[1]：根據定義, 不做任何 flip, 然後計算 nums[1] = 1 的最大連續 1 個數

    • 當 nums[1] = 0 時 ➔ noFlip[1] = 0
    • 當 nums[1] = 1 時 ➔ noFlip[1] = 1

    ➔ 由上述得到 noFlip[1] = nums[1]

  • res：上述兩者中取較大者, max(flip[1], noFlip[1]) = max(1 - nums[1], nums[1]) = 1

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        const int n = nums.size();
        vector<int> flip(n + 1, 0);
        vector<int> noFlip(n + 1, 0);

        nums.emplace(nums.begin(), 0);
        flip[1] = 1 - nums[1], noFlip[1] = nums[1];
        int res = 1;

        for (int i = 2; i <= n; ++i) {
            if (nums[i] == 0) {
                flip[i] = noFlip[i - 1] + 1;
                noFlip[i] = 0;
            } else {
                flip[i] = flip[i - 1] + 1;
                noFlip[i] = noFlip[i - 1] + 1;
            }

            res = max({res, flip[i], noFlip[i]}); // 三者中取較大者
        }

        return res;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ flip, noflip

Solution 2：

想法：改進 Solution 1, 由於 flip[i], noFlip[i] 只會用到第 i - 1 次的狀態, 因此只需儲存上一次的狀態即可, 根本不需要開到 $O(n)$ space

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        const int n = nums.size();

        nums.emplace(nums.begin(), 0);

        int flip = 1 - nums[1], noFlip = nums[1], res = 1;

        for (int i = 2; i <= n; ++i) {
            if (nums[i] == 0) {
                flip = 1 + noFlip;
                noFlip = 0;
            } else {
                ++flip;
                ++noFlip;
            }

            res = max({res, flip, noFlip}); // 三者中取較大者
        }

        return res;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間