[프로그래머스] 161988. 연속 펄스 부분 수열의 합 | DP | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

• 펄스수열이란 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열이다
• 주어진 수열에 펄스수열을 곱해 얻을 수 있는 연속 부분 수열의 합 중 최대값을 구하라

---

문제 조건

• 1 <= len(sequence) <= 500,000
• -100,000 <= sequence의 원소 <= 100,000

---

시행착오

• 연속부분수열의 합의 최대값을 구하는 방법을 몰라서 시뮬레이션을 많이 돌려봤다 

---

핵심 전략

• 주어진 수열에 1로 시작하는 펄스 수열과 -1로 시작하는 펄스수열을 곱하고 그중에서 연속부분수열의 합의 최대값을 구하면 된다
• 연속부분수열의 합은 DP로 구할 수 있다. 
  • dp[i]를 sequence[i]로 초기화
  • i = len(sequence) - 2부터 0까지 -1씩 증가. dp[i] = max(dp[i], dp[i+1] + sequence[i])
  • 연속부분수열의 합의 최대값 = max(dp)

---

소스코드

def getMaxSumOfPartialSequence(sequence):
    dp = sequence[:]
    for i in range(len(sequence)-2, -1, -1):
        dp[i] = max(dp[i], sequence[i] + dp[i+1])

    return max(dp)

def getPulseSequence(sequence, start):
    result = sequence[:]
    pulse = start
    for i in range(len(sequence)):
        result[i] = sequence[i] * pulse
        pulse *= -1

    return result

def solution(sequence):
    max1 = getMaxSumOfPartialSequence(getPulseSequence(sequence, 1))
    max2 = getMaxSumOfPartialSequence(getPulseSequence(sequence, -1))
    return max(max1, max2)