[Programmers] Q161998 연속 펄스 부분 수열의 합

[Programmers] Q161998 연속 펄스 부분 수열의 합

Question

Language: Python

Difficulty: Level 3

해당 문제는 연속된 펄스 부분의 합 중에서 가질 수 있는 최대값을 구하는 문제로, Dynamic Programming을 활용하여 문제 풀이가 가능하다.

-1부터 시작하는 경우와 1부터 시작하는 경우를 분리해서 아래와 같이 연산을 통해 최대값을 갱신할 수 있다. 기존에 누적해오던 펄스 부분의 합에 현재 값을 더한 것과 현재값만을 취할 때를 비교해서 현재 index에서 가질 수 있는 최대 부분 합을 저장하는 방식으로 진행한다.

for i in range(length):
    for j in range(2):
        dp[i][j]=max(dp[i-1][j] + sequence[i]*((-1)**(i+j)),sequence[i]*((-1)**(i+j))) 
    max_value=max(max_value,max(dp[i]))

[2, 3, -6, 1, 3, -1, 2, 4]의 경우에 대해서 위의 연산을 수행해보면 아래와 같은 결과가 도출되고, 최대값은 10이 된다.

	0	1	2	3	4	5	6	7
0	2	-1	-6	-1	3	4	6	2
1	-2	3	9	10	7	6	4	8

Solution

from math import inf
def solution(sequence):
    answer = 0
    length=len(sequence)
    
    dp=[[-inf,-inf] for _ in range(length)]
    
    dp[0]=[1*sequence[0],-1*sequence[0]]
    max_value=max(dp[0])
    
    for i in range(1,length):
        for j in range(2):
            dp[i][j]=max(dp[i-1][j] + sequence[i]*((-1)**(i+j)),sequence[i]*((-1)**(i+j)))
        
        max_value=max(max_value,max(dp[i]))
    
    answer=max_value     
    return answer