연속 펄스 부분 수열의 합 - 파이썬(Python)

문제 링크

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

프로그래머스

---

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

---

입출력 예

sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

---

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

---

풀이 과정

• 다소 뻔한 dp 문제
• 부분 수열의 합을 구해야하니, max(dp[idx-1][0], 0)와 같은 구문을 통해 전이 마이너스라면 끊어주는 것이 포인트
• -1, 1이 계속 바뀌므로 2의 나머지를 활용하여 구분

정답

def solution(sequence):
    answer = -1e9
    
    dp = [[0, 0] for _ in range(len(sequence))]
    
    dp[0][0], dp[0][1] = sequence[0]*-1, sequence[0]
    
    answer = max(answer, max(dp[0]))
    
    for idx, seq in enumerate(sequence):
        if idx == 0:
            continue
        
        # 펄스 수열이므로 계속 바꿔줘야 한다.
        if idx % 2 == 0:
            dp[idx][0] = max(dp[idx-1][0], 0) + sequence[idx]*-1
            dp[idx][1] = max(dp[idx-1][1], 0) + sequence[idx]
            
        else:
            dp[idx][0] = max(dp[idx-1][0], 0) + sequence[idx]
            dp[idx][1] = max(dp[idx-1][1], 0) + sequence[idx]*-1
            
        answer = max(answer, max(dp[idx]))
    
    
    return answer