[Leetcode] Longest Subarray of 1's After Deleting One Element

• 1 5
• nums[i] is either 0 or 1.
• backstore: 이전 연속된 1의 개수 저장
• count: 현재 연속된 1의 개수
• 0을 만나면 현재까지의 1 개수를 backstore에 저장하고 count를 리셋
• backstore + count 는 하나의 0을 삭제했을 때 얻을 수 있는 최대 연속 1의 길이

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        max_size = 0
        backstore = 0 # 이전 연속 1 개수
        if len(nums) == 1:
            return 0
        count = 0
        for i in range(0, len(nums)):

            if nums[i] == 0:
                backstore = count
                count = 0
            else:
                count += 1
            
            max_size = max(max_size, backstore + count)
        # 반드시 1 하나는 삭제해야 하므로
        if max_size == len(nums):
            max_size -= 1
        return max_size

• 윈도우 조건: 최대 1개의 0만 포함(그 0을 삭제할 예정)
• 윈도우 확장: right 포인터로 계속 확장
• 윈도우 축소: 0이 2개 이상이면 left를 이동하여 0을 1개 이하로 유지
• 결과 계산: right-left는 현재 윈도우 크기이고, 여기서 0 하나를 삭제하므로 그대로 최대 길이가 됨.

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left = 0
        max_length = 0
        zero_count = 0

        for right in range(len(nums)):
            # 윈도우 확장
            if nums[right] == 0:
                zero_count += 1
            
            # 윈도우 축소: 0이 2개 이상이면 left 이동
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            
            # 윈도우 내 0을 하나 삭제했을 때 얻을 수 있는 연속 1의 길이
            max_length= max(max_length, right-left)
        return max_length

for while 중첩이지만, right, left 포인터가 각각 n번, 최대 n번 이동하므로 총 2n, 즉 O(n) 이고, 이걸 분할상환이라고 한다.