연속 펄스 부분 수열의 합 (Python)

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

접근 방법

1. 몇 번째 요소에서 시작하던지, 수열을 1로 시작한 펄스와 -1로 시작한 펄스가 곱해진 두 개의 수열만 고려하면 됨
   1. index 값에 따라 1과 -1로 값이 교차되는 pulse 변수 사용
2. 최선의 답을 구하기 위해 0 부터 n-1까지 순회를 해야하긴 하지만, 여기서 중요한 점은 어떤 index에서 어떤 선택을 해야 최선의 답이 나올 것인지이다
   1. DP를 사용하여 각 수열에 대해서, a) 현재 index까지의 연속된 누적합 + 현재의 sequence 값 b) 현재의 sequence 값를 비교해서 더 높은 값을 기록한다.
      1. dp[i] = max( _sequence[i] , _sequence[i] + dp[i-1] )
   2. 언제 제일 높은 값이 나올 지 모르기 때문에 매 순회마다 answer, a_max, b_max의 값을 비교해준다.

코드

def solution(sequence):
    answer = -1e9
    a_max = b_max = 0
    pulse = 1
    for i in range(len(sequence)):
        a = sequence[i] * pulse
        b = sequence[i] * -pulse
        a_max = max(a, a + a_max)
        b_max = max(b, b + b_max)
        answer = max(answer, a_max, b_max)
        pulse *= -1
    return answer

후기

문제와 해결법이 직관적이지 않아 이해하기 어려웠던 문제 ㅠㅠ