1493. Longest Subarray of 1's After Deleting One Element
https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
문제
풀이(처음 풀었던 답_DFS)
Example 2 예시에서 설명하자면 다음과 같다.
0을 기준으로 left, right로 나누어서 생각해 보자
첫 번째 '0'인덱스는 0이다.
left = 0(0 이하 인덱스는 0으로 리턴)
right = [1,1,1,0,1,1,0,1]이 될 것인데 1의 개수를 세고 0이 되면 1의 개수를 리턴한다. 즉
[1,1,1] => 3을 리턴할 것이다.
두 번째 '0'인덱스는 4이다.
left = 3('0'과 '0'사이의 1의 개수)
right = [1,1,0,1]이 될 것인데 마찬가지로 [1,1] => 2를 리턴할 것이다.
마지막으로 세 번째 '0'인덱스는 7이 될 것인데
left = 2
right = [1] => 1을 리턴 할 것이다.
즉 left + right 더 한값(0+3, 3+2, 2+1) 중 최대값인 5를 리턴하면 되는 것이다.
dfs함수는 right에서 1의 개수를 리턴해주는 함수이다.
또한 flg를 사용한 이유는 nums 원소 전부 1일 경우 max값 계산을 하지 않기 때문에 flg를 사용하여 예외처리를 하였다.결과
풀이(슬라이딩 윈도우)
만약 0이 되면 기존 포인터를 옮기는 것이다. p2는 현재 인덱스이고 nums[p2] == 0이면 last_zero(최근 0 인덱스 위치) + 1로 포인터 위치를 바꿔서 최대값을 찾는 것이다.결과
풀이(DP)
dp를 그래프로 나타내면 다음과 같다.
dp1에는 1의 개수를 저장한다. dp1[0] = 1, dp1[1] = 2, dp1[2] = 0(1이 아니므로 0으로 초기화)
dp2에는 경우의 수에 맞게 최소값을 저장한다.
dp2[0] = min(0,0) + 1
dp2[1] = 0
dp2[2] = min(2,0) + 1가 될 것이다.
