연속하는 구간을 한번 뒤집어야할때 켜져있는 원소들의 합의 최댓값을 구하는 놀라운 방법

25634번: 전구 상태 뒤집기

 

 

전구의 밝기들이 배열로 주어지고, 초기에 켜져있는지, 꺼져있는지가 주어진다.

 

연속하는 구간내의 모든 전구들의 상태를 뒤집으면 켜진 전구는 꺼지고, 꺼진 전구는 켜진다.

 

이 연산을 정확히 1번 해야할때, 전구 밝기들의 합의 최댓값을 구한다.

 

----------------------------------------------------------------------------------------------------------------------------------------------------

 

n이 최대 20만인데, 연속하는 구간의 상태를 뒤집어야한다?

 

구간 dp로 하자니 O(N^2)일텐데

 

그리고 연산을 무조건 1번은 해야한다는거까지

 

굉장히 어렵다

 

처음 상태에서 밝기 합을 S라고 하고, 전구 상태를 바꿀때, 밝기의 변화량을 D라고 한다.

 

예를 들어 A = [2,3,5], B = [1,0,1]이라고 한다면, 전구 상태를 바꾸면 켜져있는 전구는 꺼지므로 

 

밝기가 -가 되어야하고, 꺼져있는 전구는 켜지므로 밝기가 +가 되어야한다.

 

D = [-2,3,-5]가 된다.

 

그러면 연속하는 구간의 전구를 뒤집는다는 것은 무엇을 의미하는가?

 

최초 밝기 상태 S에서 어떤 구간 [i,j]내의 전구들의 상태를 바꾼다면, S에서 [i,j]내의 원소들을 빼거나 더하는 것이다.

 

즉, 켜진 상태였다면 S에서 빼줘야하고, 꺼진 상태였다면 S에서 더해줘야하고

 

그러므로 S + ([i,j]내의 빼거나 더하는 양의 최댓값)이 정답이 된다.

 

그런데 ([i,j]내의 빼거나 더하는 양의 최댓값) 이 값은?

 

D배열에서 연속하는 구간내 원소 합의 최댓값과 같다.

 

이는 카데인 알고리즘을 이용하면 O(N)에 구할 수 있음이 알려져있다

 

https://deepdata.tistory.com/390

다이나믹 프로그래밍 - Kadane algorithm

 

n = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))

s = 0

D = []

for i in range(n):
    
    if B[i] == 1:
        
        s += A[i]
        D.append(-A[i])
    
    else:
        
        D.append(A[i])

INF = 10**18

dp = [-INF]*n

dp[0] = D[0]

for i in range(1,n):
    
    dp[i] = max(dp[i-1] + D[i], D[i])

print(s + max(dp))