i < j < k < l을 O(N)에 도는 미친 다이나믹 프로그래밍 테크닉

15487번: A[j]-A[i]+A[l]-A[k] (acmicpc.net)

 

크기 N인 주어진 배열 A에서 i < j < k < l인 순서쌍 (i,j,k,l)에 대하여 A[j] - A[i] + A[l] - A[k]의 최댓값을 찾는 문제

 

N은 최대 1000000이라 4중 for문으로 찾는건 당연히 불가능하다

 

A[j] - A[i]의 최댓값과 A[l] - A[k]의 최댓값을 나눠서 구하면 좋을 것 같다

 

 

근데 i < j일때, A[j] - A[i]의 최댓값도 O(N)에 구하는게 쉽지 않아보인다

 

어떻게 구할 수 있을까?

 

현재 0 ~ j 구간을 보고 있을때 A[j] - A[i]의 최댓값은, A[j] - (A[0] ~ A[j-1]중 최솟값)

 

dp[j] = i < j, i = 0,1,2,..,j-1인 모든 (i,j)에 대해 A[j] - A[i]의 최댓값이라고 정의하자.

 

j = 0, 1, 2, 3, ... 가면서 A[j]의 최솟값을 min_value로 항상 갱신해놓는다면,

 

현재 j에 대해 0~j-1까지 최솟값은 min_value이고 그러므로 A[j] - min_value로 최댓값을 구할 수 있다.

 

이를 dp[j]에 저장해놓고 다음 j+1로 가는데.. 그러면 A[j+1] - min_value를 구하면 되겠지만

 

i < j인 (i,j)에 대하여 A[j] - A[i]의 최댓값을 dp[j]로 정의하는데

 

이전에 구해놓은 dp[j]가 더 클수 있기 때문에, dp[j]과 A[j+1] - min_value를 비교해서 더 큰 값으로 갱신하면 된다

 

dp1[j] = max(dp1[j-1], A[j] - min_value)로 한다면, 모든 0~j구간의 (i,j)에 대한 최댓값을 dp1[j]에 저장할 수 있다

 

min_value = A[0]

#dp1[j] = A[j] - A[i]의 최댓값, i < j, i = 0,1,2,..,j-1
for j in range(1,n):
    
    if dp1[j-1] > A[j] - min_value:
        
        dp1[j] = dp1[j-1]
    
    else:
        
        dp1[j] = A[j] - min_value
    
    if A[j] < min_value:
        
        min_value = A[j]

 

 

똑같은 방법으로

 

dp[l] = k < l인 (k,l)에 대해 A[l] - A[k]의 최댓값으로 정의하면 구할 수 있을 것이다

 

근데 그렇게 하면 이제 문제는

 

i < j < k < l인 (i,j,k,l)에 대하여 A[j] - A[i] + A[l] - A[k]의 최댓값을 구하는게 문제다

 

i < j인 A[j] - A[i]의 최댓값과 k < l인 A[l] - A[k]의 최댓값은 알고 있는데... 이게 연결이 안된다

 

그러면 조금 생각을 바꿔서

 

dp[k] = k < l, l = k+1,k+2,...,n-1인 모든 (k,l)에 대해 A[l] - A[k]의 최댓값으로 정의해보자

 

그러면 k = n-1,n-2,...0으로 이동하면서 항상 l = k+1,k+2,..,n-1에서 A[l]의 값을 최댓값 max_value로 갱신해놓으면

 

A[l] - A[k]의 최댓값은 max_value - A[k]로 구할 수 있다

 

이를 dp[k] = max_value - A[k]로 저장해두고, 다음 k-1로 이동하면

 

max_value - A[k-1]과 dp[k]중 더 큰 값을 dp[k-1]에 저장하면 될 것이다.

 

dp[k] = max(dp[k+1], max_value - A[k])로 하면 k~n-1의 모든 (k,l)에 대하여 A[l] - A[k]의 최댓값을 저장할 수 있다

 

#dp2[k] = A[l] - A[k]의 최댓값 k < l, l = k+1,k+2,...,n-1

max_value = A[n-1]

for k in range(n-2,-1,-1):
    
    if dp2[k+1] > max_value - A[k]:
        
        dp2[k] = dp2[k+1]
    
    else:
        
        dp2[k] = max_value - A[k]
    
    if A[k] > max_value:
        
        max_value = A[k]

 

 

다음과 같이 0~j 구간의 A[j] - A[i]의 최댓값 dp1[j]와 k ~ n-1 구간의 A[l] - A[k]의 최댓값 dp2[k]를 알고 있다

 

 

그러므로 x = 0,1,2,..,n-2에 대하여 dp1[x] + dp2[x+1]은 무엇을 의미할까

 

i = 0~x-1인 모든 i에 대하여 A[x] - A[i]의 최댓값 + l = x+2,x+3,...,n-1인 모든 l에 대하여 A[l] - A[x+1]의 최댓값

 

i < x < x+1 < l인 모든 (i,x,x+1,l)에 대하여 A[x] - A[i] + A[l] - A[x+1]의 최댓값

 

근데 이렇게 하니까 i < j < k < l인 (i,j,k,l)에 대해 구해야하는데 i < j < j+1 < l인 (i,j,j+1,l)에 대해 구한것 같다

 

근데 그게 아니라

 

dp1[j] = i < j인 (i,j)에 대해 A[j] - A[i]의 최댓값

 

예를 들어 j = 3이라고 한다면 dp1[3]은... 0~3 구간의 A[j] - A[i]의 최댓값

 

0~3구간이라는건 (0,3), (1,3), (2,3)의 경우에 대해 A[j] - A[i]의 최댓값을 구한게 아니라 

 

(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)의 모든 경우에 대해 A[j] - A[i]의 최댓값을 구했다는 것

 

왜냐하면 dp1[j]를 구할때 dp1[j] = max(dp1[j-1], A[j] - min_value)로 이전 j-1과 비교해서 최댓값을 구했으니까

 

 

 

 

따라서 모든 i = 0,1,2,..,n-2에 대하여 dp1[i] + dp2[i+1]의 최댓값을 구한다면...

 

dp1[i]는 모든 i < j에 대해 최댓값을 구한거고 dp2[i+1]은 모든 j < k < l에 대해 최댓값을 구한 것이 된다

 

 

#i < j < k < l인 (i,j,k,l)에 대하여 A[j] - A[i] + A[l] - A[k]의 최댓값을 구하는 문제
n = int(input())

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

#A는 양수인데, A[j] - A[i]는 A[j] = 0, A[i] = 10000..이라 음수가 가능
INF = 10000000

dp1 = [-INF]*(n+1)
dp2 = [-INF]*(n+1)

#A[j] - A[i]의 최댓값 + A[l] - A[k]의 최댓값으로 나눠서 문제를 해결

min_value = A[0]

#dp1[j] = i < j, i = 0,1,2,..,j-1인 모든 (i,j)에 대하여 A[j] - A[i]의 최댓값
#j = 0,1,2,...,n-1일때 각각 A[i]의 최솟값에 대해 A[j] - (min_value)
#j가 커지면서 A[i]의 최솟값을 갱신
#dp1[j] = max(dp1[j-1], A[j] - min_value)하면 0~j 구간의 모든 (i,j)에 대해 최댓값
for j in range(1,n):
    
    if dp1[j-1] > A[j] - min_value:
        
        dp1[j] = dp1[j-1]
    
    else:
        
        dp1[j] = A[j] - min_value
    
    if A[j] < min_value:
        
        min_value = A[j]

#dp2[k] = k < l, l = k+1,k+2,...,n-1인 모든 (k,l)에 대해 A[l] - A[k]의 최댓값
#k = n-1,n-2,n-3,...,0에 대하여 (A의 최댓값) - A[k]
#k가 작아지면서 A[k]의 최댓값을 갱신
#dp2[k] = max(dp2[k+1], max_value - A[k])하면 k~n-1 구간의 모든 (k,l)에 대해 최댓값
max_value = A[n-1]

for k in range(n-2,-1,-1):
    
    if dp2[k+1] > max_value - A[k]:
        
        dp2[k] = dp2[k+1]
    
    else:
        
        dp2[k] = max_value - A[k]
    
    if A[k] > max_value:
        
        max_value = A[k]

answer = -INF

#dp1은 0~j구간 dp2는 k~n-1구간을 커버하므로
#dp1[i]+dp2[i+1]은 모든 i < j < k < l인 (i,j,k,l)에 대해 A[j]-A[i] + A[l]-A[k]의 최댓값이 된다
for i in range(n-1):
    
    if dp1[i] + dp2[i+1] > answer:
        
        answer = dp1[i]+dp2[i+1]

print(answer)