[프로그래머스] 연속 펄스 부분 수열의 합 (파이썬)

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/161988

난이도 : LV3

문제해결

• 이중 DP배열을 사용해서 전 단계에서 -1 을 곱했을 경우와, 1 을 곱했을 경우로 나눈다.

소스코드

def solution(seq):
    n = len(seq)
    
    dp = [[0] * n for _ in range(2)]
    
    dp[0][0] = seq[0] * -1
    dp[1][0] = seq[0]
    
    for i in range(1, n):
        dp[0][i] = max(-seq[i], dp[1][i-1] - seq[i])
        dp[1][i] = max(seq[i], dp[0][i-1] + seq[i])
    
    _max = 0
    for i in range(2):
        _max = max(max(dp[i]), _max)
    
    return _max