연속 펄스 부분 수열의 합

문제

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

접근 방식

짝수번째 인덱스마다 -1을 곱한 수열 seq1과, 홀수번째 인덱스마다 -1을 곱한 수열 seq2의 연속 부분 수열 최대 합을 구하는 문제다.

연속 부분 수열 최대 합을 구하기 위해선 DP를 활용할 수 있다.
DP[i]을 i번째까지 최대 부분 합으로 설정한다면,

현재부터 새로 시작하는 수열과, 기존 최대 합 + 현재값과 비교해서 최대값으로 갱신하면 된다.

코드

def solution(sequence):
    seq1 = [x * (-1) if i % 2 == 0 else x for i, x in enumerate(sequence)]
    seq2 = [x * (-1) if i % 2 == 1 else x for i, x in enumerate(sequence)]

    dp1, dp2 = [0] * len(sequence), [0] * len(sequence)
    dp1[0], dp2[0] = seq1[0], seq2[0]
    max_sum = max(dp1[0], dp2[0])
    for i in range(1, len(sequence)):
        dp1[i] = max(dp1[i - 1] + seq1[i], seq1[i])
        dp2[i] = max(dp2[i - 1] + seq2[i], seq2[i])

        max_sum = max(max_sum, dp1[i], dp2[i])

    return max_sum