[프로그래머스] 연속 펄스 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/161988

1) 코드

def solution(sequence):
    
    answer = -1e9

    N = len(sequence)

    ## 1, -1, 1, -1을 반복
    dp1 = [0]*N
    dp1[0] = sequence[0]
    
    ## -1, 1, -1, 1을 반복
    dp2 = [0]*N
    dp2[0] = -sequence[0]

    for i in range(1, N):
        if i % 2 == 0:
            dp1[i] = max(dp1[i-1]+sequence[i], sequence[i])
        else:
            dp1[i] = max(dp1[i-1]-sequence[i], -sequence[i])

    for i in range(1, N):
        if i % 2 == 1:
            dp2[i] = max(dp2[i - 1] + sequence[i], sequence[i])
        else:
            dp2[i] = max(dp2[i - 1] - sequence[i], -sequence[i])

    answer = max(answer, max(dp1))
    answer = max(answer, max(dp2))

    return answer

2) 해설

• 일반적인 DP 문제에서 펄스 부분 수열이라는 약간의 응용이 더해진 문제이다.
• 해당 펄스 부분 수열의 조건에 따라 +, -를 번갈아가면서 값을 구해주면 된다.