프로그래머스 [Lv. 3] 연속 펄스 부분 수열의 합 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=python3

프로그래머스

정답 코드

def solution(sequence):
    lenS = len(sequence)
    dp = [[0 for _ in range(lenS)] for _ in range(2)]
    
    dp[0][0] = sequence[0]
    dp[1][0] = sequence[0] * -1
    
    for i in range(1, lenS):
        zero = one = 1
        
        if (i % 2):
            zero = -1
        else:
            one = -1
            
        dp[0][i] = dp[0][i-1] + sequence[i] * zero
        dp[1][i] = dp[1][i-1] + sequence[i] * one
    
    maxDpZero = max(dp[0])
    maxDpOne = max(dp[1])
    minDpZero = min(dp[0])
    minDpOne = min(dp[1])
    answer = max(maxDpZero-minDpZero, maxDpOne-minDpOne, maxDpZero, maxDpOne)
    return answer

풀이 방법

1. dp를 만든다.
   1. 0번째 인덱스는 1, -1, 1, -1 ... 을 곱해서 더할 예정
   2. 1번째 인덱스느 -1, 1, -1, 1 ... 를 곱해서 더할 예정
2. dp를 완성시킨다.
3. 가장 큰 누적합에서 가장 작은 누적합을 뺀 부분이 부분 수열 과 누적합 중 가장 큰 부분 중에서 가장 큰 값을 answer에 대입하면 끝!

느낀점

• ???: 이게 되네???