홀수 길이의 연속 부분 배열의 합 중 가장 큰 값을 구하는 방법

19355번: A Really Odd Sequence (acmicpc.net)

 

주어진 배열에서 길이가 홀수인 연속 부분 배열의 원소 합 중 가장 큰 값을 구하는 문제

 

https://deepdata.tistory.com/390

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

 

카데인 알고리즘의 연장선상이긴 한데 문제는 홀수 길이여야한다는 것...

 

카데인 알고리즘은 배열의 길이를 모른다..

 

길이 정보를 담자니.. dp[i][j]로 하면 배열의 길이는 최대 n = 1000000이고.. 그러면 j도 1000000라서...

 

메모리 초과에 시간초과가 뻔한데

 

길이 자체는 안중요해서 예전에 사용하던 테크닉으로 "홀수면 0, 짝수면 1로 두면 2*n으로 줄일 수 있다"

 

dp[i][j] = i번째 원소까지 연속하는 부분 배열의 길이가 짝수이면 j = 1, 길이가 홀수이면 j = 0, 합의 최댓값 

 

원소는 -10^9부터 10^9이므로 음수도 최댓값이 될 수 있으니, 초기화할때 INF = -1000000000000으로 음수로 충분히 크게 잡아야한다

 

첫번째 원소는 홀수 길이니까 dp[0][0] = A[0], 나머지는 모두 -INF로 초기화해서...

 

i번째까지 홀수 길이의 경우는 i-1번째까지 짝수 길이의 최대합 + 현재 원소를 더하면 홀수 길이가 되니까..

 

dp[i][0] = max(dp[i-1][1] + A[i], A[i])

 

i번째까지 짝수 길이의 경우는 i-1번째까지 홀수 길이의 최대합 + 현재 원소를 더하면 짝수 길이가 되니까...

 

dp[i][1] = max(dp[i-1][0] + A[i], A[i])????

 

근데 A[i] 하나는 홀수 길이니까 dp[i][1]은 짝수 길이만 담는거니까 들어가면 안되겠지

 

dp[i][1] = dp[i-1][0] + A[i]

 

 

마지막 정답을 찾을 때는 dp[n-1][0]???

 

이건 n-1번째 원소까지, 홀수 길이의 연속하는 부분 수열 중 최대 합이지만...

 

문제는 모든 홀수 길이의 연속하는 부분 수열 중 최대 합으로.. 중간에 최대 합이 나올 수도 있기 때문에

 

모든 i = 0,1,2,..,n-1에 대해 max(dp[i][0])가 정답이 된다

 

from sys import stdin

z = int(stdin.readline())

for _ in range(z):

    n = int(stdin.readline())

    A = list(map(int,stdin.readline().split()))

    INF = 100000000000000000000000000

    dp = [[-INF]*2 for _ in range(n)]

    dp[0][0] = A[0]

    for i in range(1,n):

        dp[i][0] = max(A[i], dp[i-1][1] + A[i])
        dp[i][1] = dp[i-1][0] + A[i]
    
    answer = -INF

    for i in range(n):
        
        if answer < dp[i][0]:
            
            answer = dp[i][0]
    
    print(answer)