Max Consecutive Ones III ใน C++: หา Subarray 1s ยาวสุดหลังพลิก 0 ได้ k ตัว

โจทย์

อาร์เรย์ 0/1 สามารถพลิก 0 → 1 ได้สูงสุด k ตัว หา subarray ต่อเนื่องที่เป็น 1 ทั้งหมดยาวสุด

ตัวอย่าง: A=[1,1,1,0,0,0,1,1,1,1,0], k=2 → 6 (พลิก 2 ตัวกลางได้ 6 ตัวติดกัน)

แนวคิด: Sliding Window

รักษา window [j, i] ที่มี 0 ≤ k ตัว ขยาย i เพิ่ม 0 ให้ k-- ถ้า k < 0 → กด j ไปข้างหน้าจน k ≥ 0

ขั้นตอน

1. ans = 0, j = 0
2. ลูป i = 0 ถึง n-1:
   • ถ้า A[i] == 0 → k--
   • while j <= i && k < 0:
     • ถ้า A[j] == 0 → k++
     • j++
   • ans = max(ans, i - j + 1)
3. คืน ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestOnes(vector<int>& A, int k) {
        int ans = 0, j = 0, n = A.size();
        for (int i = 0; i < n; i++) {
            if (A[i] == 0) k--;
            while (j <= i && k < 0) {
                if (A[j] == 0) k++;
                j++;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,1,1,0,0,0,1,1,1,1,0};
    cout << ob.longestOnes(v, 3); // 10 (โจทย์ตัวอย่าง k=3)
    return 0;
}

อินพุต / เอาต์พุต

Input: [1,1,1,0,0,0,1,1,1,1,0] 3

Output: 10

ความซับซ้อน

• Time: O(n) - i และ j เดินไปข้างหน้าจบ
• Space: O(1)